QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#665670#8551. DFS Order 5WedonotLikeStudying#WA 29ms18248kbC++203.9kb2024-10-22 14:41:062024-10-22 14:41:15

Judging History

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

  • [2024-10-22 14:41:15]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:18248kb
  • [2024-10-22 14:41:06]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define per(a,b,c) for(int a=(b);a>=(c);a--)
#define db long double
#define ll long long
#define vi vector<int>
#define pb emplace_back
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;

template<class T>inline void read(T &x) {
	T f=1; x=0; char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}

const int N=1e5;
const int inf=0x3f3f3f3f;

int n,Q,k[N+5],as[N+5];

vi e[N+5],qy[N+5],qi[N+5];

int bcj[N+5],sz[N+5],fa[N+5],dfn[N+5],siz[N+5],qaq[N+5];

inline void dfs1(int x) {
	dfn[x]=(++dfn[0]); siz[x]=1;
	for(int v:e[x]) if(v!=fa[x]) {
		fa[v]=x;
		dfs1(v);
		siz[x]+=siz[v];
	}
}

int sta[N+5],top,sa[N+5],sb[N+5],sc[N+5],vs[N+5],tmd[N+5],tot,yzy[N+5];

inline int find(int x) {
	while(bcj[x]!=x) x=bcj[x];
	return x;
}

inline void meg(int x,int y) {
	x=find(x); y=find(y);
	if(sz[x]>sz[y]) swap(x,y);
	//fa[x]=y
	top++;
	sa[top]=x; sb[top]=sz[y]; sc[top]=y;
	bcj[x]=y; sz[y]+=sz[x];
}

inline int chk(int x,int y) {
	x=find(x); y=find(y);
	return (x==y);
}

inline void pop(int to) {
	while(top!=to) {
		bcj[sa[top]]=sa[top];
		sz[sc[top]]=sb[top];
		top--;
	}
}

inline void dfs2(int x) {
	for(int qid:qi[x]) {
		int Top=top;
		as[qid]=1;
		rep(i,1,k[qid]-1) if(!chk(x,fa[qy[qid][i]])) {
			as[qid]=0;
			break;
		}
		else meg(x,qy[qid][i]);
		pop(Top);
	}
	for(int v:e[x]) if(v!=fa[x]) {
		int Top=top;
		meg(v,x);
		dfs2(v);
		pop(Top);
	}
}

struct Segment_Tree {
	#define ls rt<<1
	#define rs rt<<1|1
	#define mid ((l+r)>>1)
	int vmx[(N+5)<<2],vmn[(N+5)<<2];
	Segment_Tree() {
		mem(vmx,0);
		mem(vmn,0x3f);
	}
	inline void pu_(int rt) { vmx[rt]=max(vmx[ls],vmx[rs]); vmn[rt]=min(vmn[ls],vmn[rs]); }
	inline void ins_(int rt,int l,int r,int k,int ch) {
		if(l==r) return(void)(vmx[rt]=vmn[rt]=ch);
		if(k<=mid) ins_(ls,l,mid,k,ch);
		else ins_(rs,mid+1,r,k,ch);
		pu_(rt);
	}
	inline void del_(int rt,int l,int r,int k) {
		if(l==r) return(void)(vmx[rt]=0,vmn[rt]=inf);
		if(k<=mid) del_(ls,l,mid,k);
		else del_(rs,mid+1,r,k);
		pu_(rt);
	}
	inline int qmn_(int rt,int l,int r,int L,int R) {
		if(L<=l&&r<=R) return vmn[rt];
		int ans=inf;
		if(L<=mid) ans=min(ans,qmn_(ls,l,mid,L,R));
		if(R>mid) ans=min(ans,qmn_(rs,mid+1,r,L,R));
		return ans;
	}
	inline int qmx_(int rt,int l,int r,int L,int R) {
		if(L<=l&&r<=R) return vmx[rt];
		int ans=0;
		if(L<=mid) ans=max(ans,qmx_(ls,l,mid,L,R));
		if(R>mid) ans=max(ans,qmx_(rs,mid+1,r,L,R));
		return ans;
	}
	#undef ls
	#undef rs
	#undef mid
}t;

inline bool cmp(int x,int y) {
	return dfn[x]<dfn[y];
}

inline void solve() {
	read(n); read(Q);
	rep(i,1,n-1) {
		int u,v;
		read(u); read(v);
		e[u].pb(v); e[v].pb(u);
	}
	rep(i,1,n) bcj[i]=i,sz[i]=1;
	rep(i,1,Q) {
		qy[i].clear();
		read(k[i]);
		rep(j,1,k[i]) read(qaq[j]);
		int tag=0;
		rep(j,2,k[i]) if(qaq[j]==1) {
			tag=1;
			break;
		}
		if(tag) {
			as[i]=0;
			continue;
		}
		rep(j,1,k[i]) {
			int x=qaq[j];
			qy[i].pb(x);
			if(j==1) qi[x].pb(i);
		}
	}
	dfn[0]=0;
	dfs1(1);
	dfs2(1);
	rep(i,1,Q) if(as[i]) {
		rep(j,1,k[i]) yzy[qy[i][j-1]]++;
		rep(j,1,k[i]) if(yzy[qy[i][j-1]]>1) as[i]=0;
		rep(j,1,k[i]) yzy[qy[i][j-1]]=0;
		rep(j,1,k[i]) {
			int x=qy[i][j-1];
			if(t.qmx_(1,1,n,dfn[x],dfn[x]+siz[x]-1)!=0) as[i]=0;
			t.ins_(1,1,n,dfn[x],j);
		}
		tot=0;
		rep(j,1,k[i]) {
			int x=qy[i][j-1];
			int L=t.qmn_(1,1,n,dfn[x],dfn[x]+siz[x]-1);
			int R=t.qmx_(1,1,n,dfn[x],dfn[x]+siz[x]-1);
			if((R-L)!=(siz[x]-1)) tmd[++tot]=x;
		}
		sort(tmd+1,tmd+tot+1,cmp);
		rep(j,2,tot) if(tmd[j-1]!=fa[tmd[j]]) as[i]=0;
		rep(j,1,k[i]) {
			int x=qy[i][j-1];
			t.del_(1,1,n,dfn[x]);
		}
	}
	rep(i,1,Q) if(as[i]) puts("Yes"); else puts("No");
}

int main() {
	//int T; read(T); while(T--)
	solve();
}
/*
7 1
1 2
2 4
2 6
1 3
3 5
5 7
5 2 6 4 3 5
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 29ms
memory: 18248kb

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

result:

wrong answer 2nd words differ - expected: 'No', found: 'Yes'