QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#417699 | #8716. 树 | Larunatrecy# | AC ✓ | 461ms | 41576kb | C++14 | 1.8kb | 2024-05-22 21:00:55 | 2024-05-22 21:00:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
int n,m,q,p[N];
vector<int> G[N];
void add(int x,int y)
{
G[x].push_back(y);
G[y].push_back(x);
}
int dep[N],jump[N][20],fa[N],st[N],ed[N],tot=0;
void dfs(int x,int pre)
{
st[x]=++tot;
fa[x]=pre;
dep[x]=dep[pre]+1;
jump[x][0]=pre;
for(int k=1;jump[x][k-1];k++)jump[x][k]=jump[jump[x][k-1]][k-1];
for(int y:G[x])if(y^pre)
{
dfs(y,x);
}
ed[x]=tot;
}
int jmp(int x,int y)
{
for(int k=19;k>=0;k--)
if(dep[jump[x][k]]>dep[y])x=jump[x][k];
return x;
}
bool anc(int x,int y)
{
return st[x]<=st[y]&&st[y]<=ed[x];
}
int ner(int x,int y)
{
if(anc(y,x))return jmp(x,y);
return fa[y];
}
int ans=0;
void pan(int x,int v)
{
if(x<=1||x>=m)return;
if(ner(p[x-1],p[x])==ner(p[x+1],p[x]))ans+=v;
}
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';
x=(f?-x:x);
}
int main()
{
read(n);read(m);read(q);
for(int i=1;i<n;i++)
{
int x,y;
read(x);read(y);
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1;i<=m;i++)read(p[i]);
dfs(1,0);
for(int i=1;i<=m;i++)pan(i,1);
while(q--)
{
int x,v;
read(x);read(v);
pan(x-1,-1);pan(x,-1);pan(x+1,-1);
p[x]=v;
pan(x-1, 1);pan(x, 1);pan(x+1, 1);
if(m==1)printf("%d\n",1);
else printf("%d\n",2+ans);
}
return 0;
}
/*
30 48 0
10 24
10 13
10 26
13 29
27 26
17 24
27 21
17 15
13 5
13 30
27 3
18 21
9 21
2 24
10 4
11 5
2 8
10 23
1 18
21 25
4 20
12 23
22 27
28 27
18 7
13 6
14 30
10 19
16 21
14 29 25 30 1 17 22 21 11 19 21 30 13 1 22 10 14 7 29 7 15 21 25 29 25 7 29 7 1 23 3 17 2 7 4 27 18 26 3 6 5 3 16 26 20 19 16 2
*/
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 8360kb
input:
5 5 3 2 1 3 2 1 4 5 1 1 5 4 2 3 1 3 5 3 3 3
output:
4 4 5
result:
ok 3 number(s): "4 4 5"
Test #2:
score: 0
Accepted
time: 3ms
memory: 8448kb
input:
30 200 200 10 24 10 13 10 26 13 29 27 26 17 24 27 21 17 15 13 5 13 30 27 3 18 21 9 21 2 24 10 4 11 5 2 8 10 23 1 18 21 25 4 20 12 23 22 27 28 27 18 7 13 6 14 30 10 19 16 21 14 29 25 30 1 17 22 21 11 19 21 30 13 1 22 10 14 7 29 7 15 21 25 29 25 7 29 7 1 23 3 17 2 7 4 27 18 26 3 6 5 3 16 26 20 19 16 2...
output:
174 175 175 175 175 175 175 175 175 175 176 176 176 176 176 176 175 175 175 175 174 173 173 173 173 173 173 174 174 174 174 173 173 174 174 174 174 174 174 174 174 174 173 173 173 174 173 173 174 173 174 174 174 174 174 174 174 174 174 174 174 175 174 174 174 174 174 175 175 177 177 177 177 177 176 ...
result:
ok 200 numbers
Test #3:
score: 0
Accepted
time: 81ms
memory: 9416kb
input:
1000 200000 200000 142 266 266 877 877 673 673 473 923 473 923 55 55 288 679 288 85 679 85 460 296 460 793 296 262 793 40 262 40 680 647 680 999 647 56 999 550 56 550 774 774 939 939 423 423 168 168 554 554 93 329 93 329 474 221 474 890 221 890 304 752 304 345 752 345 269 290 269 290 781 781 264 859...
output:
133598 133598 133598 133598 133598 133598 133596 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133596 133596 133596 133596 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133596 133596 133596 133596 133596...
result:
ok 200000 numbers
Test #4:
score: 0
Accepted
time: 29ms
memory: 9276kb
input:
1000 200000 200000 911 577 911 775 845 911 911 780 911 585 786 911 725 911 960 911 911 645 949 911 46 911 911 429 714 911 911 703 999 911 911 194 166 911 984 911 911 262 902 911 911 201 680 911 637 911 911 923 697 911 911 534 911 38 911 743 911 762 911 342 911 983 911 758 911 716 48 911 27 911 491 9...
output:
199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810 199810...
result:
ok 200000 numbers
Test #5:
score: 0
Accepted
time: 40ms
memory: 9412kb
input:
1000 200000 200000 481 469 250 469 751 469 932 751 469 496 779 932 932 277 154 481 836 932 313 496 157 250 723 277 496 625 824 723 252 496 932 50 836 349 313 348 580 252 277 381 183 932 648 252 824 81 250 310 338 154 481 441 932 772 779 534 310 972 513 836 98 534 678 183 902 469 349 370 380 348 751 ...
output:
193586 193586 193586 193585 193586 193586 193586 193586 193586 193586 193586 193586 193586 193586 193586 193587 193588 193588 193588 193588 193588 193588 193588 193588 193587 193588 193588 193589 193589 193589 193589 193589 193589 193590 193590 193590 193590 193590 193590 193590 193590 193590 193590...
result:
ok 200000 numbers
Test #6:
score: 0
Accepted
time: 36ms
memory: 9284kb
input:
1000 200000 200000 135 730 730 138 545 135 179 730 170 135 282 545 282 852 852 664 61 664 243 664 852 68 838 135 68 822 282 370 698 135 179 304 170 225 496 664 179 234 545 397 950 397 698 550 304 987 730 605 671 698 730 458 550 318 170 754 243 468 159 671 852 414 159 928 61 443 664 705 234 75 170 47...
output:
197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197896 197897 197897 197897 197897 197897 197897 197897 197897 197897 197897 197897 197897 197897 197897...
result:
ok 200000 numbers
Test #7:
score: 0
Accepted
time: 461ms
memory: 41576kb
input:
200000 200000 200000 14041 108064 14041 6424 164394 6424 118940 164394 118940 153965 71525 153965 71525 23275 23275 136661 136661 78274 75990 78274 75990 39081 163771 39081 163771 159683 159683 104966 104966 15146 15146 85180 181282 85180 181282 44830 44830 86055 86055 164641 18858 164641 18858 1800...
output:
133599 133599 133599 133599 133599 133599 133599 133597 133597 133597 133595 133595 133593 133595 133595 133595 133595 133595 133595 133595 133595 133595 133595 133595 133595 133595 133595 133595 133595 133595 133595 133595 133595 133593 133593 133593 133593 133591 133591 133591 133591 133591 133591...
result:
ok 200000 numbers
Test #8:
score: 0
Accepted
time: 74ms
memory: 34312kb
input:
200000 200000 200000 62780 76814 47775 76814 110514 76814 115498 76814 76814 185747 76814 76605 76814 153854 61935 76814 76814 22798 191569 76814 84863 76814 65861 76814 182858 76814 164850 76814 170036 76814 76814 171051 76814 177452 76176 76814 76814 148390 76814 152812 76814 11154 76814 134237 13...
output:
199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999 199999...
result:
ok 200000 numbers
Test #9:
score: 0
Accepted
time: 94ms
memory: 34444kb
input:
200000 200000 200000 99629 142514 178276 142514 115655 142514 99629 178074 178276 175567 70738 175567 115655 129972 89322 129972 169894 129972 147071 129972 10566 175567 107243 129972 8907 142514 7782 169894 110752 7782 147071 76195 115655 114377 7782 121893 101071 10566 84377 121893 175567 160127 1...
output:
197382 197381 197381 197382 197382 197382 197382 197382 197382 197382 197382 197382 197382 197382 197382 197382 197382 197382 197382 197382 197382 197382 197382 197381 197381 197381 197381 197381 197380 197380 197380 197380 197380 197380 197380 197380 197380 197380 197380 197380 197380 197380 197380...
result:
ok 200000 numbers
Test #10:
score: 0
Accepted
time: 95ms
memory: 34384kb
input:
200000 200000 200000 43091 180583 9077 43091 53566 9077 9077 167067 53566 19150 23945 53566 19150 154823 43091 175394 23945 53451 8199 180583 165028 8199 142301 8199 134062 53566 42947 154823 53451 70553 19150 171332 8199 134312 134062 53691 142301 185642 153308 70553 142301 107541 53566 172393 1651...
output:
199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974 199974...
result:
ok 200000 numbers
Test #11:
score: 0
Accepted
time: 68ms
memory: 33548kb
input:
200000 1 200000 197983 124070 174059 197983 10252 197983 20970 197983 160835 10252 174059 165013 152731 165013 10252 56326 152731 125850 20970 82906 114208 174059 28990 124070 28990 5953 9385 125850 174059 198622 151867 198622 23092 56326 55184 124070 18287 160835 135931 10252 104549 55184 82256 198...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 200000 numbers
Test #12:
score: 0
Accepted
time: 77ms
memory: 33584kb
input:
200000 2 200000 29068 50187 50187 120936 163187 50187 186138 50187 29068 115846 5735 29068 152896 50187 115846 24968 151823 24968 183803 163187 29068 152721 152721 47799 29068 196869 29068 152775 5023 186138 27368 24968 115846 112237 13012 50187 112237 85883 24968 51691 61801 183803 112237 85045 521...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 200000 numbers
Test #13:
score: 0
Accepted
time: 84ms
memory: 33548kb
input:
200000 3 200000 79577 85741 164484 79577 41699 79577 132056 41699 39180 132056 182376 41699 97496 39180 164484 132037 45902 85741 183818 97496 182376 91448 135302 97496 85566 164484 56863 91448 41699 34451 132056 105308 164884 164484 135302 52544 8156 85741 187216 79577 79577 154465 90451 164484 391...
output:
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
result:
ok 200000 numbers
Extra Test:
score: 0
Extra Test Passed