QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#417103 | #8716. 树 | FlyingFeather | WA | 1715ms | 29264kb | C++17 | 3.0kb | 2024-05-22 14:24:02 | 2024-05-22 14:24:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int>v[N];
int a[N],b[N],depth[N],fa[N][16];
void bfs(int root)
{
memset(depth,0x3f,sizeof depth);
depth[0] = 0,depth[root] = 1;
queue<int> q;
q.push(root);
while(q.size())
{
int t = q.front();
q.pop();
for(auto j:v[t])
{
if(depth[j]>depth[t]+1)
{
depth[j] = depth[t]+1;
q.push(j);
fa[j][0] = t;
for(int k=1;k<=15;k++)
{
fa[j][k] = fa[fa[j][k-1]][k-1];
}
}
}
}
}
int lca(int a, int b)
{
if (depth[a] < depth[b]) swap(a, b);
for (int k = 15; k >= 0; k -- )
if (depth[fa[a][k]] >= depth[b])
a = fa[a][k];
if (a == b) return a;
for (int k = 15; k >= 0; k -- )
if (fa[a][k] != fa[b][k])
{
a = fa[a][k];
b = fa[b][k];
}
return fa[a][0];
}
int cal(int i)
{
if(b[i]==0)
{
if(b[i+1]==0) return 0;
else if(b[i+1]==1) return 1;
else return 1;
}
else if(b[i]==1)
{
if(b[i+1]==0)
{
if(lca(a[i],a[i+2])==a[i]||lca(a[i],a[i+2])==a[i+2]) return 1;
else
{
if(lca(a[i],a[i+2])==a[i+1]) return 0;
return 1;
}
}
else if(b[i+1]==1) return 0;
else return 0;
}
else
{
if(b[i+1]==0) return 0;
else if(b[i+1]==1) return 1;
else return 1;
}
}
int main()
{
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
v[x].push_back(y),v[y].push_back(x);
}
bfs(1);
for(int i=1;i<=m;i++) cin>>a[i];
for(int i=1;i<m;i++)
{
if(lca(a[i],a[i+1])==a[i]) b[i]=0;
else if(lca(a[i],a[i+1])==a[i+1]) b[i]=1;
else b[i]=2;
}
if(m<=2)
{
for(int i=1;i<=q;i++) cout<<m<<endl;
return 0;
}
int ans=2;
//for(int i=1;i<m;i++) cout<<b[i]<<" ";
//cout<<endl;
for(int i=1;i<m-1;i++) ans+=cal(i);
//cout<<ans<<endl;
while(q--)
{
int idx,x,num1=0,num2=0;
cin>>idx>>x;
for(int i=max(1,idx-3);i<=min(idx+3,m-2);i++) num1+=cal(i);
a[idx]=x;
for(int i=max(1,idx-3);i<=min(idx+3,m-1);i++)
if(lca(a[i],a[i+1])==a[i]) b[i]=0;
else if(lca(a[i],a[i+1])==a[i+1]) b[i]=1;
else b[i]=2;
/*cout<<"a:";
for(int i=1;i<=m;i++) cout<<a[i]<<" ";
cout<<endl;
cout<<"b:";
for(int i=1;i<m;i++) cout<<b[i]<<" ";
cout<<endl;*/
for(int i=max(1,idx-3);i<=min(idx+3,m-2);i++) num2+=cal(i);
ans+=num2-num1;
cout<<ans<<endl;
}
}
/*
5 5 3
2 1
3 2
1 4
5 1
1 5 4 2 3
1 3
5 3
3 3
*/
/*
4 3 1
1 2
2 3
2 4
3 1 4
*/
/*
8 6 4
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3 4 5 6 7
*/
/*
30 3 1
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
30 1 17
*/
//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
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 11832kb
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: 0ms
memory: 12496kb
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: 290ms
memory: 11500kb
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: 236ms
memory: 11640kb
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: 337ms
memory: 11172kb
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: 327ms
memory: 11376kb
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: -100
Wrong Answer
time: 1715ms
memory: 29264kb
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:
134960 134960 134960 134960 134960 134960 134960 134959 134960 134960 134959 134959 134957 134957 134957 134958 134959 134958 134958 134957 134957 134957 134957 134957 134956 134956 134956 134956 134956 134957 134957 134957 134956 134954 134954 134954 134954 134953 134953 134953 134953 134953 134954...
result:
wrong answer 1st numbers differ - expected: '133599', found: '134960'