QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#748733#8551. DFS Order 5000226#WA 26ms13780kbC++172.4kb2024-11-14 21:14:372024-11-14 21:14:38

Judging History

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

  • [2024-11-14 21:14:38]
  • 评测
  • 测评结果:WA
  • 用时:26ms
  • 内存:13780kb
  • [2024-11-14 21:14:37]
  • 提交

answer

#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
#define lowbit(x) (x&(-x))
using namespace std;

const int maxn=1e5+10;

int n,q;
set<int>S[maxn];

struct BIT{
	int c[maxn];
	vector<pii>vec;
	void Add(int x,int d){
		for(;x<=n;x+=lowbit(x))c[x]+=d;
	}
	int Query(int x){
		int res=0;for(;x;x-=lowbit(x))res+=c[x];
		return res;
	}
	void Clear(){ for(auto it : vec)Add(it.fir,it.sec); vec.resize(0); }
}T;

struct Graph{
	vector<int>E[maxn];
	void lqx(int u,int v){ E[u].emplace_back(v);S[u].insert(v); }
	int fa[maxn],top[maxn],siz[maxn],dfn[maxn],Te,rk[maxn],son[maxn],dep[maxn];
	void Dfs1(int u){
		siz[u]=1;dep[u]=dep[fa[u]]+1;
		for(auto v :E[u])if(v!=fa[u]){
			fa[v]=u;Dfs1(v);siz[u]+=siz[v];
			if(!son[u] || siz[v]>siz[son[u]])son[u]=v;
		}
	}
	void Dfs2(int u,int tp){
		top[u]=tp;dfn[u]=++Te;rk[Te]=u;
		if(son[u])Dfs2(son[u],tp);
		for(auto v : E[u])if(v!=fa[u] && v!=son[u]){
			Dfs2(v,v);
		}
	}
	int Lca(int u,int v){
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]])swap(u,v);
			u=fa[top[u]];
		}
		return dep[u]<dep[v] ? u : v;
	}
	int Kth(int u,int k){
		while(k){
			if(k>=dep[u]-dep[top[u]]){
				k-=(dep[u]-dep[top[u]]);
				u=top[u];
			}else {
				return rk[dfn[u]-k];
			}
			if(!k)break;
			--k;u=fa[u];
		}
		return u;
	}
	bool Jump(int &u,int v){
		if(T.Query(dfn[v]))return false;
		int lf=Lca(u,v);
		if(lf==v)return false;
		if(lf==u){
			if(S[u].count(v))return u=v,true;
			else return false;
		}
		if((E[u].size()>1))return false;
		if(!S[lf].count(v))return false;
		int p=Kth(u,dep[u]-dep[lf]-1);
		
		T.Add(dfn[p],1);T.vec.emplace_back(dfn[p],-1);
		T.Add(dfn[p]+siz[p],-1);T.vec.emplace_back(dfn[p]+siz[p],1);
		u=v;return true;
	}
}G;

void solve(){
	cin>>n>>q;Rep(i,2,n){ int u,v;cin>>u>>v;G.lqx(u,v),G.lqx(v,u); }
	G.Dfs1(1),G.Dfs2(1,1);
	while(q--){
		int len;cin>>len;
		int u;cin>>u;bool flag=true;
		Rep(i,2,len){
			int v;cin>>v;
			if(!flag)continue;
			flag=G.Jump(u,v);
		}
		if(flag)cout<<"Yes\n";
		else cout<<"No\n";

		T.Clear();
	}
}

int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 11840kb

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: 26ms
memory: 13780kb

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
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

wrong answer 899th words differ - expected: 'No', found: 'Yes'