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;
inline int read() {
    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];
int e_size,head[M],fa[M],pre[M];
struct node {
	int x,y;
	
	inline void in() {
		x=read(),y=read();
		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) {
	e[++e_size]=(edge){v,head[u]};
	head[u]=e_size;
}

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) {
	for(int i=head[x];i;i=e[i].nxt) {
		int v=e[i].v;
		if(v==ha[x]) continue;
		ha[v]=x,dfs1(v,ha);
	}
}

inline void dfs2(int x) {
	vis[x]=1;
	for(int i=head[x];i;i=e[i].nxt) {
		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));
	memset(head,0,sizeof(head));
	re[x]=1;
	++du[x],++du[y];
	e_add(x,y),e_add(y,x);
	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];
		e_add(u,v),e_add(v,u);
	}
	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);
	int Test_=read();
	while (Test_--) {
		n=read();
		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));
				memset(head,0,sizeof(head));
				for1(1,n-1,j) e_add(b[j].x,b[j].y),e_add(b[j].y,b[j].x);
				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
Task F - Grafting
User asd123www
Language C++14 (GCC 5.4.1)
Score 1900
Code Size 2660 Byte
Status
Exec Time 47 ms
Memory 256 KB

Test Cases

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