QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#666046 | #8551. DFS Order 5 | WedonotLikeStudying# | WA | 23ms | 7752kb | C++20 | 3.2kb | 2024-10-22 16:24:53 | 2024-10-22 16:24:59 |
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,qx[N+5];
vi e[N+5];
int dep[N+5],fa[N+5],siz[N+5],son[N+5],top[N+5],dfn[N+5],vs[N+5],tg[N+5],al[N+5],nd[N+5],sz,t1[N+5],t2[N+5],ss[N+5];
inline void dfs1(int x) {
siz[x]=1;
for(int v:e[x]) if(v!=fa[x]) {
fa[v]=x;
dep[v]=dep[x]+1;
dfs1(v);
siz[x]+=siz[v];
if(siz[v]>siz[son[x]]) son[x]=v;
}
}
inline void dfs2(int x,int topf) {
top[x]=topf; dfn[x]=(++dfn[0]);
if(son[x]) dfs2(son[x],topf);
for(int v:e[x]) if(v!=fa[x]&&v!=son[x]) dfs2(v,v);
}
inline int LCA(int x,int y) {
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
int val[N+5];
inline int lo(int x) { return (x&(-x)); }
inline void upd(int x,int ch) { while(x<=n) val[x]+=ch,x+=lo(x); }
inline int qry(int x) { int ans=0; while(x) ans+=val[x],x-=lo(x); return ans; }
inline int chk(int Fa,int x) { return (dfn[x]>=dfn[Fa])&&((dfn[Fa]+siz[Fa]-1)>=dfn[x]); }
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);
}
dfs1(1); dfs2(1,1);
rep(i,1,n) ss[i]=e[i].size()-1;
ss[1]++;
rep(asd_a,1,Q) {
int k,Tag=0;
read(k);
rep(i,1,k) read(qx[i]);
rep(i,1,k) tg[qx[i]]=0,t1[qx[i]]=0,t2[qx[i]]=0;
rep(i,1,k) tg[qx[i]]++;
rep(i,1,k) if(tg[qx[i]]>1) {
Tag=1;
break;
}
rep(i,1,k) {
int x=qx[i];
int Sz=qry(dfn[x]+siz[x]-1)-qry(dfn[x]-1);
upd(dfn[x],1);
if(Sz) Tag=1;
}
rep(i,1,k) upd(dfn[qx[i]],-1);
if(Tag) {
puts("No");
continue;
}
per(i,k,1) {
int x=qx[i];
upd(dfn[x],1);
int Sz=qry(dfn[x]+siz[x]-1)-qry(dfn[x]-1);
if(Sz==siz[x]) t1[x]=1;
else t1[x]=0;
}
rep(i,1,k) upd(dfn[qx[i]],-1),t2[qx[i]]=0;
per(i,k,1) {
int x=qx[i],pos=i+1;
if(!t1[x]) continue;
if(siz[x]==1) {
t2[x]=1;
continue;
}
t2[x]=1;
rep(j,1,ss[x]) {
if(fa[qx[pos]]!=x) {
t2[x]=0;
break;
}
if(!t2[qx[pos]]) {
t2[x]=0;
break;
}
pos+=siz[qx[pos]];
}
}
rep(i,1,k) if(t1[qx[i]]!=t2[qx[i]]) {
Tag=1;
break;
}
if(Tag) {
puts("No");
continue;
}
sz=0;
for(int i=1;i<=k;) {
nd[++sz]=qx[i];
if(!t1[qx[i]]) break;
i+=siz[qx[i]];
}
int lca=nd[1];
rep(i,2,sz) {
int Lca=LCA(lca,nd[i]);
if(chk(lca,nd[i])) Tag=1;
else if(fa[nd[i]]!=Lca) Tag=1;
lca=Lca;
}
if(Tag) {
puts("No");
continue;
}
int pos=1,Pos=nd[sz];
rep(i,1,k) if(qx[i]==nd[sz]) pos=i+1;
for(;pos<=k;) {
if(fa[qx[pos]]!=Pos) {
Tag=1;
break;
}
if(t2[qx[pos]]) pos+=siz[qx[pos]];
else Pos=qx[pos],pos++;
}
if(Tag) puts("No");
else puts("Yes");
}
}
int main() {
//int T; read(T); while(T--)
solve();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7752kb
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: 23ms
memory: 5712kb
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 1919th words differ - expected: 'Yes', found: 'No'