QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#749197#8551. DFS Order 5000226WA 30ms16600kbC++173.9kb2024-11-14 23:01:102024-11-14 23:01:11

Judging History

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

  • [2024-11-14 23:01:11]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:16600kb
  • [2024-11-14 23:01:10]
  • 提交

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 Lim;
	int R;
	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)){
				if(Lim)Lim=(T.Query(1,1,n,dfn[u]+1,dfn[u]+siz[u]-1)-T.Query(1,1,n,dfn[v],dfn[v]+siz[v]-1)==siz[u]-siz[v]-1);
				u=v;
				return true;
			}
			else return false;
		}
		if((E[u].size()>1))return false;
		if(!S[lf].count(v))return false;
		if((!ch) && (!Lim) && 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);
		if((!ch) && (!Lim)){
				if(dep[lf]<dep[fa[u]] && T.Query(1,1,n,dfn[p]+1,dfn[p]+siz[p]-1)!=siz[p]-1)return false;
		}
		if(Lim){
			if(dep[lf]<=dep[R])R=lf;
			else Lim=false;
		}
		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;G.Lim=true;
		int u;cin>>u;bool flag=true;G.R=u;
		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; }

詳細信息

Test #1:

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

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: 14508kb

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