QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #88408 | #5830. 树 | aoui | 20 | 1824ms | 489888kb | C++20 | 2.3kb | 2023-03-16 10:23:58 | 2023-03-16 10:24:02 |
Judging History
answer
#include<cstdio>
#include<algorithm>
using namespace std;
namespace IO{
const int sz=1<<22;
char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
inline char gc(){
return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
}
template<class T> void read(T& x){
x=0; char c=gc();
for(;c<'0'||c>'9';c=gc());
for(;c>='0'&&c<='9';c=gc())
x=x*10+(c-'0');
}
inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
template<class T> void write(T x,char c='\n'){
if(x<0) pc('-'), x=-x;
if(x==0) pc('0'); int t=0;
for(;x;x/=10) p[++t]=x%10+'0';
for(;t;--t) pc(p[t]); pc(c);
}
struct F{~F(){flush();}}f;
}
using IO::read;
using IO::write;
const int N=1e6+5;
int n,Q,dt[N],ne[N],ff[N],fa[N][22],ta[N][22],dep[N],qq[N];
long long tag[N],a[N],f[N][22],ans;
#include<vector>
vector<int> to[N],d[N];
#include<queue>
queue<int> q;
void bfs()
{
for(int i=1;i<=n;i++)d[i].push_back(0);
q.push(1);
while(q.size())
{
int x=q.front();
q.pop();
qq[++qq[0]]=x;
dep[x]=dep[ff[x]]+1;
ne[x]=d[dep[x]][dt[dep[x]]];
f[x][0]=f[ne[x]][0]+a[x];
d[dep[x]].push_back(x);
dt[dep[x]]++;
for(int y:to[x])q.push(y);
}
for(int i=1;i<=n;i++)
{
for(int j=1,k=1;j<=dt[i];j++)
{
for(int x:to[d[i][j]])tag[x]=1;
for(;k<=dt[i+1]&&tag[d[i+1][k]];k++);
ta[d[i][j]][0]=d[i+1][k-1];
for(int x:to[d[i][j]])tag[x]=0;
}
}
}
int main()
{
read(n);
for(int i=1;i<=n;i++)read(a[i]);
for(int i=2;i<=n;i++)read(ff[i]),to[ff[i]].push_back(i),fa[i][0]=ff[i];
for(int j=1;j<=20;j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
bfs();
for(int j=1;j<=20;j++)
{
for(int i=1;i<=n;i++)tag[i]=0;
for(int i=1;i<=n;i++)
{
int tt=0;
if(a[i]&(1<<j-1))tt=-(1<<j-1);
else tt=1<<j-1;
tag[fa[i][j-1]]+=tt;
tag[fa[i][j]]-=tt;
}
for(int i=n;i>=1;i--)
for(int x:to[i])tag[i]+=tag[x];
tag[0]=0;
for(int i=1;i<=n;i++)tag[qq[i]]+=tag[ne[qq[i]]];
for(int i=1;i<=n;i++)
ta[i][j]=ta[ta[i][j-1]][j-1],f[i][j]=f[i][j-1]+f[ta[i][j-1]][j-1]+tag[i];
}
read(Q);
while(Q--)
{
int x,y,d;
read(x);read(d);
y=ne[x];
d++;
ans=0;
for(int i=20;i>=0;i--)
if((1<<i)<=d)
{
ans+=f[x][i]-f[y][i];
x=ta[x][i];
y=ta[y][i];
d-=1<<i;
}
write(ans);
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 11ms
memory: 50612kb
input:
2000 946347867 341162491 202762650 295215762 254064439 66267204 693162580 357612557 492940637 939526638 59775103 374919339 144042807 861369313 651043728 999024805 439554916 167782038 597475252 56704409 69846137 22185655 79439847 769194737 145071391 226046618 915359433 392527325 84982946 54584098 827...
output:
31727996583 558747809 12352523 864526657454 91729844170 585197158 1628586765 922104954 8179033998 55032863007 1832814618 1719999175 57622640021 2418952903 118234180121 87152233736 403506296965 1458062157 139639462250 708763390 974312741 22160481331 541384937 113212699950 755479297 465075002 51201629...
result:
wrong answer 1st numbers differ - expected: '31727996563', found: '31727996583'
Test #2:
score: 0
Wrong Answer
time: 136ms
memory: 96440kb
input:
99999 792064428 473106195 799314986 65440734 948726345 442414256 280245405 873012700 466192412 899092866 283555341 657824017 963883713 793944180 767444438 105576842 542107696 580140098 65321660 381184238 584604194 397414881 861590124 309323011 217641157 120832524 303744205 961590116 110259426 380351...
output:
2509771019 102808896825 528899856 125427731 1953894159 2464509568850 5038222768168 586671581 4009894234253 798898621 468901916 1620113250 25990778 1594379150 3312692738611 30663600816263 1721547881 1491500623 2600435006438 15307884754142 263989598 1350176621 1471646904305 727716410 2234098330759 184...
result:
wrong answer 2nd numbers differ - expected: '102808896745', found: '102808896825'
Test #3:
score: 0
Runtime Error
input:
1000000 947727010 179844140 923847675 171881267 5552129 974443359 989307850 869400987 126992154 527448411 141137718 136124474 917813105 392020809 79012342 473860575 969007624 833563354 90169336 878445705 84352622 403307122 733751738 670851448 942399068 731541999 101293644 545785337 964751520 9168003...
output:
result:
Test #4:
score: 0
Runtime Error
input:
1000000 264862971 751386013 921867736 711577153 262726588 565608444 975324815 440219681 107888226 928241413 729126923 283912914 86248857 896446999 12839598 651796991 139813366 105131395 341646170 839485925 939265720 844548518 102280410 457829889 8602879 737140565 17206920 974175632 535833885 8373832...
output:
result:
Test #5:
score: 0
Wrong Answer
time: 1477ms
memory: 489888kb
input:
1000000 978606419 773027389 111265179 979476504 280718851 476857501 751854950 579263969 848569548 781051974 31782627 533831186 812822170 111553645 297770650 331144396 676977983 2236128 258203325 75591120 676466973 60056446 494411414 286185093 92474576 173276071 535648669 87210101 355790411 880267291...
output:
2258826661 938786622 1803221827 20412967770 11943681457 2783437365 16665953888 2720451454 1859550937 476794111 986063591 1579646964 14494868601 38176990 781099105 527479272 2392930136 2519423494 1620138021 23553905550 5107065102 6903424079 1206547828 18830610787 49589751 499629803 4275328263 1379311...
result:
wrong answer 4th numbers differ - expected: '20412967786', found: '20412967770'
Test #6:
score: 10
Accepted
time: 1481ms
memory: 489828kb
input:
1000000 952470566 585754087 120174600 401525004 458588768 5487567 31210348 446333263 231409083 521960132 457721893 866842852 925207283 16805978 4706826 99640835 619272676 136536623 459247161 308807462 633687300 717271369 23906473 865522890 173799280 424309108 719410673 118906385 110627845 730629403 ...
output:
994051214 904057442 2995278795 3980490219156 35388089564067 976251948 369701890 43760580 1510389651 3077329408 66354186603909 716198149 190685967 105215742257612 13827392197052 557364187 1084839575 3104092 276690929 98459972717615 467852673 33049527 425554649 22790861096838 97736610924937 426018723 ...
result:
ok 1000000 numbers
Test #7:
score: 10
Accepted
time: 1508ms
memory: 489724kb
input:
1000000 732367509 105027907 958920212 886798715 102486738 813075884 301085392 242303497 979657287 944859684 307768 438158233 561755409 740706505 791145209 283862713 828081846 771569552 59044985 600549571 191330226 438693570 36976319 810654215 220068818 771875421 740642902 839964155 206129566 2065543...
output:
999908753 401770479 206278425790162 194002588398182 57017982421941 107873913740677 1146711843 100798039882905 2910590132 4981801495 1079679207 2140524944 75514756 9410084351477 74281057669756 167205592 58363655788956 1085743066 51861395060073 416905260757083 99153021379917 990736484 4798942061 37301...
result:
ok 1000000 numbers
Test #8:
score: 0
Wrong Answer
time: 1700ms
memory: 489644kb
input:
1000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1697981969 1779147606 21336579 14 5469179670 27641383 0 111909113 25588 1 3 1 1 1 1 0 637250745 1 0 1672119899 8 0 0 1 0 112015289 1 0 0 0 0 337651064 360223550 0 107946 94085646 6 22296018 22532043 1 1 21176396 344677455 1 1449681648 0 442673934 2 1 2 8950694197 6 5401594277 0 9690053703 5706426645...
result:
wrong answer 1st numbers differ - expected: '3826404725', found: '1697981969'
Test #9:
score: 0
Wrong Answer
time: 1690ms
memory: 489348kb
input:
1000000 465660691 982007525 816592310 377030959 572981469 679249520 86377999 709561525 940473306 35102782 886143915 792819787 903287397 264564177 857982095 91486434 217197704 123118964 383387342 820268798 497623987 255010796 607884194 848568529 38169627 197987657 421323589 664004905 485409127 696844...
output:
96094115967 8243991660413 82893021916767 34208171963511 275400654 1384234656 64716568 11773599384148 10114549262708 263845835152 15632079882918 528398853 1456723423 1214744688 12973183835679 23475037 28419067678887 245789356 109738951 48543617711895 81139259926881 102619945 17650378219377 1556076353...
result:
wrong answer 1st numbers differ - expected: '96094116015', found: '96094115967'
Test #10:
score: 0
Wrong Answer
time: 1824ms
memory: 489388kb
input:
1000000 665830082 788228483 245541444 289601309 641764988 150723484 925214020 557415731 310210969 379707835 517820381 883917428 134445288 775557009 444476671 89856268 655841087 888410254 37788122 694551869 563331754 488108584 839551943 415095075 445425438 35452604 562044723 640544531 146258096 66852...
output:
431856043 520373616 77562427496991 7077779345165 63182568437650 13801713122004 762015332 4985151929605 1184478776 594507511 2675566544361 25669164561590 306250439 62500137 75019033279108 786078000 31380422716168 4162775188 4984310921230 877965179 18603382041516 1013123764 8945453563365 5683574405715...
result:
wrong answer 3rd numbers differ - expected: '77562434895287', found: '77562427496991'