QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#691998#8551. DFS Order 5szy10010WA 31ms30424kbC++233.3kb2024-10-31 13:36:152024-10-31 13:36:16

Judging History

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

  • [2024-10-31 13:36:16]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:30424kb
  • [2024-10-31 13:36:15]
  • 提交

answer

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define u1 (u<<1)
#define u2 (u<<1|1)
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
int h[N],e[N],ne[N],idx;
int depth[N],fa[N][20],sz[N],cnt[N],son[N];
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
void bfs(int root)
{
	memset(depth,0x3f,sizeof(depth));
	depth[0]=0;
	depth[root]=1;
	queue<int>q;
	q.push(root);
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=h[t];~i;i=ne[i])
		{
			int j=e[i];
			if(depth[j]>depth[t]+1)
			{
				depth[j]=depth[t]+1;
				q.push(j);
				fa[j][0]=t;
				for(int i=1;i<=19;i++)
					fa[j][i]=fa[fa[j][i-1]][i-1];
			}
		}
	}
	return;
}
//int la(int a,int dep)
//{
//	for(int i=19;i>=0;i--)
//		if(fa[a][i]<=dep)
//			a=fa[a][i];
//	return a;
//}
int la(int v, int d) {
	for (int k = 20; k >= 0; --k) {
		if (d >= (1 << k)) {
			v = fa[v][k];
			d -= (1 << k);
		}
	}
	return v;
}
int lca(int a,int b)
{
	if(depth[a]<depth[b])swap(a,b);
	for(int i=19;i>=0;i--)
		if(depth[fa[a][i]]>=depth[b])a=fa[a][i];
	if(a==b)return a;
	for(int i=19;i>=0;i--)
		if(fa[a][i]!=fa[b][i])
			a=fa[a][i],b=fa[b][i];
	return fa[a][0];
}
void dfs(int u,int fa)
{
	sz[u]=1;
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j==fa)continue;
		dfs(j,u);
		sz[u]+=sz[j];
	}
	return ;
}
void solve()
{
	memset(h,-1,sizeof(h));
	cin>>n>>m;
	_rep(i,2,n)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	bfs(1);
	dfs(1,0);
	while(m--)
	{
		cin>>n;
		bool bl=true;
		int pre=0;
		vector<int>v;
		_rep(i,1,n)
			cin>>son[i],cnt[son[i]]=1;
		_rep(i,1,n)
		{
			if(pre)
			{
				if(pre==fa[son[i]][0])
				{
					v.pb(son[i]);
					pre=son[i];
					continue;
				}
				else
				{
					bool pan=true;
					int lc=lca(pre,son[i]);
					int lc_1=la(pre,depth[son[i]]+1);
					while(v.size())
					{
						if(depth[v.back()]<depth[son[i]])break;
						cnt[fa[v.back()][0]]+=cnt[v.back()];
						if(cnt[v.back()]!=sz[v.back()])
						{
							cout<<v.back()<<" "<<cnt[v.back()]<<" "<<sz[v.back()]<<'\n';
							pan=false;
							break;
						}
						v.pp;
					}
					if(!pan||!fa[son[i]]||fa[son[i]][0]!=lc)
					{
//						cout<<son[i]<<" "<<cnt[lc_1]<<" "<<sz[lc_1]<<endl;
						bl=false;
						break;
					}
					v.pb(son[i]);
				}
			}
			pre=son[i];
		}
		_rep(i,1,n)cnt[son[i]]=0;
		if(bl)cout<<"Yes\n";
		else cout<<"No\n";
	}
	return ;
}
signed main()
{
	IOS;
	int T=1;
//	cin>>T;
	while(T--)
		solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6 7
1 2
1 3
2 4
3 5
2 6
2 4 1
2 4 2
2 4 3
2 4 4
2 4 5
2 4 6
6 1 2 6 4 3 5

output:

No
No
Yes
No
No
Yes
Yes

result:

ok 7 tokens

Test #2:

score: -100
Wrong Answer
time: 31ms
memory: 30424kb

input:

10 100000
7 2
1 7
7 10
8 6
8 7
1 3
4 5
9 5
5 8
8 8 9 7 2 8 1 6 1
4 8 3 5 2
6 7 10 3 9 9 1
1 1
8 10 3 2 9 3 8 7 3
7 5 6 2 8 5 9 1
6 3 4 6 2 1 3
5 8 9 2 4 9
1 3
2 1 5
5 8 5 1 7 9
10 5 2 9 2 6 4 10 6 3 8
3 4 5 8
2 8 4
9 4 10 1 2 4 3 3 6 3
1 3
6 1 1 6 8 3 1
3 7 3 2
3 9 1 5
4 3 7 8 10
9 4 2 3 10 2 5 4 3 ...

output:

No
No
No
Yes
No
5 2 3
No
No
No
Yes
No
5 1 3
No
No
No
No
No
Yes
No
No
No
8 1 5
No
No
No
No
8 1 5
No
No
8 1 5
No
No
No
No
Yes
No
Yes
8 1 5
No
No
No
No
No
No
Yes
No
8 1 5
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
7 2 8
No
No
No
No
No
No
No
No
No
No
7 1 8
No
No
No
No
No
Yes
No
No
Yes
Yes
No
No
8 1 ...

result:

wrong answer 6th words differ - expected: 'No', found: '5'