QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#613301 | #8551. DFS Order 5 | ucup-team3651 | WA | 39ms | 29712kb | C++20 | 3.2kb | 2024-10-05 13:53:46 | 2024-10-05 13:53:47 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array
#define IL inline
#define mod 998244353
#define N 200005
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
void write(int x){
if(x<0)x=-x,putchar('-');
if(x/10)write(x/10);
putchar(x%10+'0');
}
struct BIT{
int K[N],tp;
pi sta[N];
int lowbit(int x){return x&(-x);}
void add(int x,int val,int opt=0){if(!opt)sta[++tp]=mp(x,val);while(x<N){K[x]+=val;x+=lowbit(x);}}
int ask(int x){int ans=0;while(x){ans+=K[x];x-=lowbit(x);}return ans;}
void resume(){while(tp)add(sta[tp].fi,-sta[tp].se,1),tp--;}
}T,G;
vi e[N];
int son[N],siz[N],lef[N],f[21][N],dep[N];
void dfs(int x,int fa){
siz[x]=1;int cnt=0;
f[0][x]=fa;dep[x]=dep[fa]+1;
for(auto v:e[x]){
if(v==fa)continue;
dfs(v,x);siz[x]+=siz[v];
if(siz[v]>siz[son[x]])son[x]=v;
cnt++;
}
if(!cnt)lef[x]++;
}
int L[N],R[N],tot,top[N],fat[N];
void dfs2(int x,int fa,int topx){
L[x]=R[x]=++tot;top[x]=topx;fat[x]=fa;
if(son[x])dfs2(son[x],x,topx),R[x]=R[son[x]];
for(auto v:e[x]){
if(v==fa || v==son[x])continue;
dfs2(v,x,v);R[x]=R[son[x]];
}
}
void add(int x){
while(x){
int anc=top[x];
T.add(L[anc],1);T.add(L[x]+1,-1);
x=fat[anc];
}
}
int a[N];
int main(){
#ifdef EAST_CLOUD
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
int n=read(),q=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
e[u].pb(v);e[v].pb(u);
}
dfs(1,0);dfs2(1,0,1);
for(int i=1;i<=20;i++){
for(int j=1;j<=n;j++)f[i][j]=f[i-1][f[i-1][j]];
}
for(int i=1;i<=q;i++){
int m=read();T.resume();G.resume();
for(int j=1;j<=m;j++)a[j]=read();
int flag=0,las=a[1],llas=a[1];add(a[1]);G.add(L[a[1]],1);
for(int j=2;j<=m;j++){
G.add(L[a[j]],1);
if(T.ask(L[a[j]])){flag=1;break;}
if(fat[a[j]]==las)las=a[j],T.add(L[a[j]],1),T.add(L[a[j]]+1,-1);
else{
if(!lef[las]){flag=1;break;}
int anc=las;
for(int i=20;i>=0;i--){
if(dep[f[i][anc]]>=dep[a[j]])anc=f[i][anc];
}
if(fat[a[j]]!=fat[anc]){flag=1;break;}
int chk=(dep[anc]>dep[llas]?anc:llas);
if(G.ask(R[chk])-G.ask(L[chk]-1)!=R[chk]-L[chk]+1){flag=1;break;}
T.add(L[anc],1);T.add(R[anc]+1,-1);las=a[j];
if(L[a[j]]<L[llas] || L[a[j]]>R[llas])llas=a[j];
}
}
if(flag)printf("No\n");
else printf("Yes\n");
}
}
//cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
//cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 28428kb
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: 29712kb
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 899th words differ - expected: 'No', found: 'Yes'