Contest Duration: ~ (local time) (140 minutes) Back to Home

Submission #3223134

Source Code Expand

Copy
```#include <bits/stdc++.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define for1(a,b,i) for(int i=a;i<=b;++i)
#define FOR2(a,b,i) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
int f=1,sum=0;
char x=getchar();
for(;(x<'0'||x>'9');x=getchar()) if(x=='-') f=-1;
for(;x>='0'&&x<='9';x=getchar()) sum=sum*10+x-'0';
return f*sum;
}

#define M 55
int n;
int du[M];
bool vis[M],re[M];
struct node {
int x,y;

inline void in() {
if(x>y) swap(x,y);
}
inline bool operator <(const node &a) const {
if(x!=a.x) return x<a.x;
return y<a.y;
}
}a[M],b[M];

struct edge {int v,nxt;}e[M*2];

inline void e_add(int u,int v) {
}

inline bool check() {
for1(1,n-1,i) if(a[i].x!=b[i].x||a[i].y!=b[i].y) return 0;
return 1;
}

inline void dfs1(int x,int *ha) {
int v=e[i].v;
if(v==ha[x]) continue;
ha[v]=x,dfs1(v,ha);
}
}

inline void dfs2(int x) {
vis[x]=1;
int v=e[i].v;
if(v==pre[x]||fa[v]!=x) continue;
dfs2(v);
}
}

inline int calc_(int x,int y) {
e_size=0;
memset(re,0,sizeof(re));
memset(du,0,sizeof(du));
memset(vis,0,sizeof(vis));
memset(pre,0,sizeof(pre));
re[x]=1;
++du[x],++du[y];
for1(1,n-1,i) {
int u=a[i].x;
int v=a[i].y;
if(u==x||v==x) continue;
++du[u],++du[v];
}
dfs1(x,pre),dfs2(x);
//for1(1,n,i) cout<<pre[i]<<" "; cout<<endl;
int cnt=0,now=0;
for1(1,n,i) now+=vis[i];
cnt=now;
while (now!=n) {
int pos=0;
for1(1,n,i) if(!vis[i]&&vis[fa[i]]&&!re[i]&&du[i]==1) {pos=i;break;}
if(!pos) break;
//cout<<pos<<" "<<pre[pos]<<endl;
re[pos]=vis[pos]=1,++now;
--du[pre[pos]],++du[fa[pos]];
}
return now==n?n-cnt+1:1e9;
}

int main () {
//	freopen("a.in","r",stdin);
while (Test_--) {
for1(1,n-1,i) a[i].in();
for1(1,n-1,i) b[i].in();
sort(a+1,a+n),sort(b+1,b+n);

if(check()) puts("0");
else {
int shu[M]={0};
for1(1,n-1,i) ++shu[a[i].x],++shu[a[i].y];
int ans=1e9;
for1(1,n,i) if(shu[i]==1) {
e_size=0;
memset(fa,0,sizeof(fa));
dfs1(i,fa);
for1(1,n,j) if(i!=j) {
int num=calc_(i,j);
ans=min(ans,num);
}
}
if(ans==1e9) ans=-1;
printf("%d\n",ans);
}
}
}```

#### Submission Info

Submission Time 2018-09-19 09:34:16+0900 F - Grafting asd123www C++14 (GCC 5.4.1) 1900 2660 Byte AC 47 ms 256 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
All 1900 / 1900 sample_01.txt, sample_02.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
test_01.txt 35 ms 256 KB
test_02.txt 36 ms 256 KB
test_03.txt 30 ms 256 KB
test_04.txt 41 ms 256 KB
test_05.txt 29 ms 256 KB
test_06.txt 34 ms 256 KB
test_07.txt 39 ms 256 KB
test_08.txt 31 ms 256 KB
test_09.txt 31 ms 256 KB
test_10.txt 37 ms 256 KB
test_11.txt 14 ms 256 KB
test_12.txt 9 ms 256 KB
test_13.txt 12 ms 256 KB
test_14.txt 17 ms 256 KB
test_15.txt 13 ms 256 KB
test_16.txt 9 ms 256 KB
test_17.txt 11 ms 256 KB
test_18.txt 5 ms 256 KB
test_19.txt 6 ms 256 KB
test_20.txt 10 ms 256 KB
test_21.txt 40 ms 256 KB
test_22.txt 41 ms 256 KB
test_23.txt 45 ms 256 KB
test_24.txt 43 ms 256 KB
test_25.txt 39 ms 256 KB
test_26.txt 40 ms 256 KB
test_27.txt 43 ms 256 KB
test_28.txt 43 ms 256 KB
test_29.txt 40 ms 256 KB
test_30.txt 47 ms 256 KB