QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#623365#8716. 树bruteforce_WA 1ms3632kbC++202.1kb2024-10-09 11:32:432024-10-09 11:32:43

Judging History

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

  • [2024-10-09 11:32:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3632kb
  • [2024-10-09 11:32:43]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18,mod=998244353,S=21;
int n,m,Q;
vector<vector<int>> e,fa;
vector<int> dep;
void dfs(int u)
{
	dep[u]=dep[fa[u][0]]+1;
	for(auto v:e[u])
	{
		if(v==fa[u][0]) continue;
		fa[v][0]=u;
		dfs(v);
	}
	for(int i=1; i<S; i++)
	{
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=S-1; i>=0; i--)
	{
		if(dep[fa[x][0]]>=dep[y])
		{
			x=fa[x][0];
		}
	}
	if(x==y) return x;
	for(int i=S-1; i>=0; i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
void O_o()
{
	cin>>n>>m>>Q;
	e.assign(n+1,vector<int>());
	fa.assign(n+1,vector<int>(S,0));
	dep.assign(n+1,0);
	for(int i=1; i<n; i++)
	{
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1);
	vector<int> b(2*m),ls(2*m);
	vector<bool> del(2*m,0);
	cin>>b[1];
	for(int i=2; i<=m; i++)
	{
		cin>>b[i*2-1];
		b[i*2-2]=lca(b[i*2-3],b[i*2-1]);
	}
	ls[2]=1;
	int tot=0;
	for(int i=2; i<2*m-1; i++)
	{
		int l1=lca(b[ls[i]],b[i]),l2=lca(b[i],b[i+1]),l3=lca(b[ls[i]],b[i+1]);
		if((l1==b[i]||l2==b[i]||l3==b[i])&&b[ls[i]]!=b[i+1])
		{
//			if(i&1)
//				cout<<i/2+1<<"\n";
			del[i]=1;
			tot++;
			ls[i+1]=ls[i];
		}
		else
		{
			del[i]=0;
			ls[i+1]=i;
		}
	}
//	cout<<2*n-1-tot<<"\n";
	while(Q--)
	{
		int id,x;
		cin>>id>>x;
		id=id*2-1;
		b[id]=x;
		if(id>1)
		{
			b[id-1]=lca(b[id-2],b[id]);
		}
		if(id<m*2-1)
		{
			b[id+1]=lca(b[id],b[id+2]);
		}
		for(int i=max(2ll,id-4); i<=min(2*m-1,id+4); i++)
		{
			tot-=del[i];
			int l1=lca(b[ls[i]],b[i]),l2=lca(b[i],b[i+1]),l3=lca(b[ls[i]],b[i+1]);
			if((l1==b[i]||l2==b[i]||l3==b[i])&&b[ls[i]]!=b[i+1])
			{
				del[i]=1;
				tot++;
				ls[i+1]=ls[i];
			}
			else
			{
				del[i]=0;
				ls[i+1]=i;
			}
		}
		cout<<2*n-1-tot<<"\n";
	}
}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cout<<fixed<<setprecision(12);
	int T=1;
//	cin>>T;
	while(T--)
	{
		O_o();
	}
}


















詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

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: -100
Wrong Answer
time: 1ms
memory: 3632kb

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:

-192
-191
-191
-191
-192
-192
-192
-191
-191
-191
-190
-190
-190
-190
-191
-192
-193
-193
-193
-193
-194
-195
-195
-195
-195
-196
-196
-196
-196
-195
-195
-196
-197
-196
-196
-196
-195
-195
-195
-195
-195
-195
-196
-196
-195
-194
-195
-194
-193
-194
-193
-193
-195
-196
-195
-195
-195
-194
-194
-194
...

result:

wrong answer 1st numbers differ - expected: '174', found: '-192'