QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#665670 | #8551. DFS Order 5 | WedonotLikeStudying# | WA | 29ms | 18248kb | C++20 | 3.9kb | 2024-10-22 14:41:06 | 2024-10-22 14:41:15 |
Judging History
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'