QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#613491#8551. DFS Order 5ucup-team3651WA 38ms28804kbC++203.2kb2024-10-05 14:05:342024-10-05 14:09:14

Judging History

你现在查看的是最新测评结果

  • [2024-10-05 14:09:14]
  • 评测
  • 测评结果:WA
  • 用时:38ms
  • 内存:28804kb
  • [2024-10-05 14:05:34]
  • 提交

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[v];
    }
}

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: 28804kb

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: 38ms
memory: 26932kb

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 19443rd words differ - expected: 'No', found: 'Yes'