QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#693632#8551. DFS Order 5sdmrlhTL 0ms20028kbC++142.4kb2024-10-31 16:29:562024-10-31 16:29:59

Judging History

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

  • [2024-10-31 16:29:59]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:20028kb
  • [2024-10-31 16:29:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld%lld",&x,&y)
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pf(x) printf("%lld",x)
#define pii pair<int,int> 
#define f first 
#define s second
#define int long long



//
const int N = 1e5+10,M=2*N;
unordered_map<int,int> ve[N];
int h[N],e[M],ne[M],idx;
int si[N],q[M],depth[N],dis[N],fa[N][30];
int now[N],nn,bl;
vector<int> c;
//
void add(int a,int b)
{
	ne[idx]=h[a],e[idx]=b,h[a]=idx++;
}

void no()
{
	cout<<"No"<<endl;
	bl=1;
}

void dfs(int u,int fa)
{
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j==fa) continue;
		ve[u][j]=1;
		dfs(j,u);
		si[u]+=si[j];
	}
}
void bfs(int root)
{
	memset(depth, 0x3f, sizeof depth);
	depth[0] = 0, depth[root] = 1;
	int hh = 0, tt = 0;
	q[0] = root;
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		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[ ++ tt] = 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];
}

bool panduan(int l,int r)
{ 
	int now=c[l];
	int nn = l;
	while(nn!=r)
	{
		if(nn>r) return 0;
		if(ve[now].count(c[nn+1]))
		{
			if(!panduan(nn+1,nn+si[c[nn+1]])) return 0;
			nn = nn+si[c[nn+1]];
		}
	}
	return 1;
	
}

//


void solve()
{
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=m;i++) h[i]=-1,si[i]=1;
	for(int i=1;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b),add(b,a);
	}
	dfs(1,-1);
	bfs(1);	
	while(n--)
	{
		cin>>nn;
		for(int i=1;i<=nn;i++) cin>>now[i];	
		int l=1,r = 1,last=-1;
		while(l<=nn)
		{
			bl=0;
			if(last!=-1&&(lca(now[1],now[l])==now[l]||lca(fa[last][0],fa[now[l]][0])!=fa[now[l]][0])){
				no();
				break;
			}
			r=l;
			last=now[l];
			c.clear();
			for(int i=l;i<=min(nn,l+si[now[l]]-1);i++,r++)
				c.push_back(now[i]);
			l=r;
			if(!panduan(0,c.size()-1)) {
				no();
				break;
			}
		}
		if(!bl) cout<<"Yes"<<endl;
	}
}
signed main()
{
	IOS;
	int _=1;
	while(_--)
		solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Time Limit Exceeded

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:


result: