QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#430971 | #4878. Easy Problem | grass8cow | WA | 9ms | 36880kb | C++17 | 3.1kb | 2024-06-04 19:16:47 | 2024-06-04 19:16:47 |
Judging History
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&∈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