QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#417103#8716. 树FlyingFeatherWA 1715ms29264kbC++173.0kb2024-05-22 14:24:022024-05-22 14:24:03

Judging History

你现在查看的是最新测评结果

  • [2024-05-22 14:24:03]
  • 评测
  • 测评结果:WA
  • 用时:1715ms
  • 内存:29264kb
  • [2024-05-22 14:24:02]
  • 提交

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'