QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#654822 | #8551. DFS Order 5 | include_BM | WA | 10ms | 13652kb | C++14 | 2.0kb | 2024-10-18 22:24:34 | 2024-10-18 22:24:34 |
Judging History
answer
//People who believe in miracles are as amazing as miracles themselves.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
const int N=2e5+10,LOG=20;
int n,m,vc[N],num,siz[N],fa[N][LOG],dep[N],ans,vis[N]; vector<int> G[N];
void dfs(int x,int fa){
siz[x]=1,::fa[x][0]=fa,dep[x]=dep[fa]+1;
for(int j=1;j<LOG;++j) ::fa[x][j]=::fa[::fa[x][j-1]][j-1];
for(auto y:G[x]) if(y!=fa) dfs(y,x),siz[x]+=siz[y];
}
inline bool check_x_is_ys_nfa(int x,int y){
for(int j=LOG-1;~j;--j)
if(dep[fa[y][j]]>=dep[x]) y=fa[y][j];
return x==y;
}
inline bool check_jump(int x,int y){
if(check_x_is_ys_nfa(x,y)) return 0;
return check_x_is_ys_nfa(fa[x][0],y);
}
bool check(int x,int l,int r){
if(vc[l]!=x) return 0;
for(int i=l+1;i<=r;){
if(fa[vc[i]][0]!=x) return 0;
if(i+siz[vc[i]]-1>=r) return check(vc[i],i,r);
if(!check(vc[i],i,i+siz[vc[i]]-1)) return 0;
i+=siz[vc[i]];
}
return 1;
}
inline void solve(){
n=read(),m=read();
for(int u,v,i=1;i<n;++i){
u=read(),v=read();
G[u].emplace_back(v),G[v].emplace_back(u);
}
dfs(1,0);
for(;m;--m){
num=read(),ans=1;
for(int i=1;i<=num;++i) vc[i]=read(),ans&=(!vis[vc[i]]++);
for(int i=1;;){
if(i+siz[vc[i]]-1>=num){ans&=check(vc[i],i,num);break;}
ans&=check(vc[i],i,i+siz[vc[i]]-1);
if(!ans||!check_jump(vc[i+siz[vc[i]]],vc[i])){ans=0;break;}
i+=siz[vc[i]];
}
if(ans) puts("Yes"); else puts("No");
for(int i=1;i<=num;++i) vis[vc[i]]=0;
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("../1.in","r",stdin);
freopen("../1.out","w",stdout);
#endif
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12556kb
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: 10ms
memory: 13652kb
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 Yes No No No No No No No ...
result:
wrong answer 89th words differ - expected: 'No', found: 'Yes'