QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#578205 | #8551. DFS Order 5 | gungod# | WA | 39ms | 12472kb | C++14 | 1.6kb | 2024-09-20 17:21:10 | 2024-09-20 17:21:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int Y,m,pos,a[N],dep[N],anc[N][21],siz[N];
set<int>son[N];
vector<int>G[N];
void Dfs(int u) {
siz[u]=1;
for(int i=1;i<=20;i++) anc[u][i]=anc[anc[u][i-1]][i-1];
for(auto v:G[u]) if(!dep[v]) {
dep[v]=dep[u]+1;
son[u].insert(v);
anc[v][0]=u;//cout<<u<<" "<<v<<endl;
Dfs(v);
siz[u]+=siz[v];
}
}
int lca(int u,int v) {
if(dep[u]>dep[v]) swap(u,v);
for(int i=20;i>=0;i--) if(dep[anc[v][i]]>=dep[u]) v=anc[v][i];
if(u==v) return v;
for(int i=20;i>=0;i--) if(anc[v][i]^anc[u][i]) u=anc[u][i],v=anc[v][i];
return anc[u][0];
}
void DFS(int u) {
while(pos<=Y&&son[u].count(a[pos])) {
DFS(a[pos++]);
}
}
bool chk1(int x) {
Y=x+siz[a[x]]-1;
pos=x+1;
DFS(a[x]);
return pos>Y;
}
bool chk2(int x) {
for(int j=1;j<x;j++) if(lca(a[j],a[x])==a[x]) return false;
Y=m;
pos=x+1;
DFS(a[x]);
return pos>Y;
}
void main1() {
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
for(int i=1;;) {
if(i+siz[a[i]]-1>=m) {
if(!chk2(i)) puts("No");
else puts("Yes");
return ;
}
else {
//cout<<"flag" <<a[i]<<" "<<a[i+siz[a[i]]]<<" "<<lca(a[i],a[i+siz[a[i]]])<<" "<<anc[a[i+siz[a[i]]]][0]<<endl;
if(!chk1(i)) return puts("No"),void();
if(lca(a[i],a[i+siz[a[i]]])!=anc[a[i+siz[a[i]]]][0]) return puts("No"),void();
i+=siz[a[i]];
}
}
}
int main() {
int n,q;
scanf("%d%d",&n,&q);
for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
dep[1]=1;
Dfs(1);
for(int _=1;_<=q;_++) {
main1();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10896kb
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: 39ms
memory: 12472kb
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 Yes 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 ...
result:
wrong answer 20th words differ - expected: 'No', found: 'Yes'