QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#748957#8551. DFS Order 5000226#WA 30ms16500kbC++173.6kb2024-11-14 22:08:522024-11-14 22:08:56

Judging History

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

  • [2024-11-14 22:08:56]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:16500kb
  • [2024-11-14 22:08:52]
  • 提交

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 Seg{
	struct tree{ int val,lazy; }tr[maxn<<2];
	void Pushup(int rt){ tr[rt].val=tr[rt<<1].val+tr[rt<<1|1].val; }
	void Build(int rt,int l,int r){
		tr[rt].lazy=-1;
		if(l==r)return;
		int mid=(l+r)>>1;
		Build(rt<<1,l,mid),Build(rt<<1|1,mid+1,r);
	}
	void Update(int rt,int l,int r,int w){
		tr[rt].val=w*(r-l+1);
		tr[rt].lazy=w;
	}
	void Pushdown(int rt,int l,int r){
		if(tr[rt].lazy==-1)return;
		int mid=(l+r)>>1;
		Update(rt<<1,l,mid,tr[rt].lazy);
		Update(rt<<1|1,mid+1,r,tr[rt].lazy);
		tr[rt].lazy=-1;
	}
	void Modify(int rt,int l,int r,int s,int t,int w){
		if(s<=l && t>=r)return Update(rt,l,r,w);
		int mid=(l+r)>>1;
		Pushdown(rt,l,r);
		if(s<=mid)Modify(rt<<1,l,mid,s,t,w);
		if(t>mid)Modify(rt<<1|1,mid+1,r,s,t,w);
		Pushup(rt);
	}
	int Query(int rt,int l,int r,int s,int t){
		if(s<=l && t>=r)return tr[rt].val;
		int mid=(l+r)>>1,res=0;
		Pushdown(rt,l,r);
		if(s<=mid)res=Query(rt<<1,l,mid,s,t);
		if(t>mid)res+=Query(rt<<1|1,mid+1,r,s,t);
		return res;
	}
}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,bool ch){
		if(T.Query(1,1,n,dfn[v],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;
		if((!ch) && dep[lf]< dep[fa[u]] && T.Query(1,1,n,dfn[fa[u]]+1,dfn[fa[u]]+siz[fa[u]]-1)!=siz[fa[u]]-1)return false;
		int p=Kth(u,dep[u]-dep[lf]-1);
		T.Modify(1,1,n,dfn[p],dfn[p]+siz[p]-1,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);
	T.Build(1,1,n);
	while(q--){
		int len;cin>>len;
		int u;cin>>u;bool flag=true;
		Rep(i,2,len){
			T.Modify(1,1,n,G.dfn[u],G.dfn[u],1);
			int v;cin>>v;
			if(!flag)continue;
			flag=G.Jump(u,v,i==2);
		}
		if(flag)cout<<"Yes\n";
		else cout<<"No\n";
		T.Update(1,1,n,0);
	}
}

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: 0ms
memory: 12532kb

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: 30ms
memory: 16500kb

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 572nd words differ - expected: 'Yes', found: 'No'