QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#430971#4878. Easy Problemgrass8cowWA 9ms36880kbC++173.1kb2024-06-04 19:16:472024-06-04 19:16:47

Judging History

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

  • [2024-06-04 19:16:47]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:36880kb
  • [2024-06-04 19:16:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
vi g[100100],g2[101000],dp[101000],h[101000];
int n,m,fa[100100];
#define pb push_back
void dfs(int x){
    for(int v:g2[x])if(v!=fa[x]){fa[v]=x,dfs(v);}
}
vi vc[201000],pt[200100],vc2[201000];
int L,R,is[201000];
bool ans;
int tt,vis[201000];
int hd[1010000],to[20100000],nxt[20100000],cn,flow[20010000];
const int I=1e9;
void ad(int u,int v,int w){
    to[++cn]=v,nxt[cn]=hd[u],flow[cn]=w,hd[u]=cn;
    to[++cn]=u,nxt[cn]=hd[v],flow[cn]=0,hd[v]=cn;
}
int S,T,d[1001000],cur[1010000];
bool bfs(){
    for(int i=1;i<=T;i++)d[i]=0,cur[i]=hd[i];queue<int>q;q.push(S),d[S]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=hd[u];i;i=nxt[i])if(flow[i]&&!d[to[i]])
            d[to[i]]=d[u]+1,q.push(to[i]);
    }
    return d[T]>0;
}
int dfs(int u,int in){
    if(u==T)return in;
    int out=0;
    for(int i=hd[u];i&&in;i=nxt[i]){
        hd[u]=i;
        if(flow[i]&&d[to[i]]==d[u]+1){
        int p=dfs(to[i],min(in,flow[i]));
        in-=p,out+=p;
        flow[i]-=p,flow[i^1]+=p;
        }
    }
    if(!out)d[u]=0;
    return out;
}
int dinic(){
    int out=0;
    while(bfs())out+=dfs(S,I);
    return out;
}
void dfs2(int x,int f){
    for(int v:g[x])if(v!=f)dfs2(v,x);
    if(ans)return;
    vi gi;gi.clear();
    for(int v:g[x])if(v!=f)gi.pb(v);R=gi.size();
    dp[x].resize(2*(m-1));for(int &o:dp[x])o=0;
    for(int i=0;i<(m-1)*2;i++){
        L=vc[i].size();
        if(!L){dp[x][i]=1;continue;}
        if(L>R)continue;
        cn=1,S=L+R+1,T=S+1;
        for(int j=1;j<=T;j++)hd[j]=0;
        for(int j=1;j<=L;j++)ad(j,T,1);
        for(int j=1;j<=R;j++)ad(S,j+L,1);
        for(int j=1;j<=L;j++)
            for(int k=1;k<=R;k++)if(dp[gi[k-1]][vc[i][j-1]])ad(k+L,j,I);
        dp[x][i]=(dinic()==L);
    }
    for(int i=1;i<=m;i++){
        L=vc2[i].size();if(L>R)continue;
        for(int j=1;j<=R;j++)is[j]=0;
        cn=1,S=L+R+1,T=S+1;
        for(int j=1;j<=T;j++)hd[j]=0;
        for(int j=1;j<=L;j++)ad(j,T,1);
        for(int j=1;j<=R;j++)ad(S,j+L,1);
        for(int j=1;j<=L;j++)
            for(int k=1;k<=R;k++)if(dp[gi[k-1]][vc2[i][j-1]])ad(k+L,j,I);
        if(dinic()==L){ans=1;return;}
    }
}
void sol(){
    scanf("%d",&n);for(int i=0;i<=n;i++)g[i].clear(),dp[i].clear();
    for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),g[u].pb(v),g[v].pb(u);
    scanf("%d",&m);for(int i=1;i<=m;i++)g2[i].clear(),vc2[i].clear();
    for(int i=1,u,v;i<m;i++)scanf("%d%d",&u,&v),g2[u].pb(v),g2[v].pb(u);
    dfs(1);
    for(int i=0;i<=m*2;i++)vc[i].clear();
    for(int i=2;i<=m;i++)for(int o=0;o<2;o++){
        int h=i*2+o;
        if(!o){for(int v:g2[i])if(v!=fa[i])vc[h-4].pb(v*2-4);}
        else{
            int f=fa[i];
            for(int v:g2[f])if(v!=i){if(fa[f]==v)vc[h-4].pb(f*2-4+1);else vc[h-4].pb(v*2-4);}
        }
    }
    for(int i=1;i<=m;i++)for(int v:g2[i])vc2[i].pb((v==fa[i])?(i*2+1-4):(v*2-4));
    ans=0,dfs2(1,0);
    puts(ans?"Yes":"No");
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 9ms
memory: 36880kb

input:

1
4 3
3 3 2 2
1 2 2
3 3 3
2 2 4

output:

Yes

result:

wrong output format Expected integer, but "Yes" found