Submission #3228539


Source Code Expand

Copy
#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
struct Info{int nu,ne;}a1[110],a2[110],a3[110];
int t,n,ansn,va[53],vb[53],ua[53],ub[53],f[53],b1[53],b2[53],b3[53],num1,num2,num3,su,p[53];
bool vi[53][53],fi[53];
void jb1(int x,int y){a1[++num1].nu=y;a1[num1].ne=b1[x];b1[x]=num1;}
void jb2(int x,int y){a2[++num2].nu=y;a2[num2].ne=b2[x];b2[x]=num2;}
void jb3(int x,int y){a3[++num3].nu=y;a3[num3].ne=b3[x];b3[x]=num3;}
void dfs(int x,int fa){
	fi[x]=true;su++;
	for (int y=b2[x];y;y=a2[y].ne)
		if (a2[y].nu!=fa&&vi[x][a2[y].nu])dfs(a2[y].nu,x);
}
void dfs1(int x,int fa){
	for (int y=b1[x];y;y=a1[y].ne){
		if (a1[y].nu!=fa){
			if (!fi[x])jb3(x,a1[y].nu);
			dfs1(a1[y].nu,x);
		}
	}
}
void dfs2(int x,int fa){
	for (int y=b2[x];y;y=a2[y].ne){
		if (a2[y].nu!=fa){
			if (!fi[x])jb3(a2[y].nu,x);
			dfs2(a2[y].nu,x);
		}
	}
}
bool dfs3(int x,int co){
	p[x]=co;
	for (int y=b3[x];y;y=a3[y].ne){
		if (p[a3[y].nu]==0){
			if (!dfs3(a3[y].nu,co))return false;
		}else{
			if (p[a3[y].nu]==co)return false;
		}
	}
	return true;
}
bool pan(){
	int l=0;
	for (int i=1;i<=n;i++)p[i]=0;
	for (int i=1;i<=n;i++){
		if (p[i]==0){
			if (!dfs3(i,++l))return false;
		}
	}
	return true;
}
int work(int x){
	for (int i=1;i<=n;i++)b1[i]=0,b2[i]=0,b3[i]=0;num1=num2=num3=su=0;
	for (int i=1;i<n;i++){jb1(va[i],ua[i]);jb1(ua[i],va[i]);}
	for (int i=1;i<n;i++){vi[va[i]][ua[i]]=true;vi[ua[i]][va[i]]=true;}
	for (int i=1;i<n;i++){jb2(vb[i],ub[i]);jb2(ub[i],vb[i]);}
	for (int i=1;i<=n;i++) fi[i]=false;
	dfs(x,0);dfs1(x,0);dfs2(x,0);
	for (int i=1;i<n;i++){vi[va[i]][ua[i]]=false;vi[ua[i]][va[i]]=false;}
	if (pan()){return n-su;}return INF;
}
int main(){
	cin>>t;
	while (t--){
		cin>>n;ansn=INF;memset(f,0,sizeof(f));memset(vi,false,sizeof(vi));
		for (int i=1;i<n;i++){scanf("%d %d",&va[i],&ua[i]);f[va[i]]++;f[ua[i]]++;}
		for (int i=1;i<n;i++)scanf("%d %d",&vb[i],&ub[i]);
		for (int i=1;i<=n;i++)ansn=min(ansn,work(i));
		for (int i=1;i<=n;i++)
			if (f[i]==1)for (int j=1;j<=n;j++)
				if (i!=j)for (int k=1;k<=n;k++){
						if (va[k]==i){int p=ua[k];ua[k]=j;ansn=min(ansn,work(i)+1);ua[k]=p;}
						if (ua[k]==i){int p=va[k];va[k]=j;ansn=min(ansn,work(i)+1);va[k]=p;}
					}
		if (ansn==INF) cout<<"-1"<<endl;else cout<<ansn<<endl;
	}
	return 0;
}

Submission Info

Submission Time
Task F - Grafting
User jah_melon
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2331 Byte
Status
Exec Time 39 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:53: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   for (int i=1;i<n;i++){scanf("%d %d",&va[i],&ua[i]);f[va[i]]++;f[ua[i]]++;}
                                                     ^
./Main.cpp:67:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   for (int i=1;i<n;i++)scanf("%d %d",&vb[i],&ub[i]);
                                                    ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
All 0 / 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 34 ms 256 KB
test_02.txt 32 ms 256 KB
test_03.txt 32 ms 256 KB
test_04.txt 33 ms 256 KB
test_05.txt 34 ms 256 KB
test_06.txt 34 ms 256 KB
test_07.txt 36 ms 256 KB
test_08.txt 35 ms 256 KB
test_09.txt 34 ms 256 KB
test_10.txt 36 ms 256 KB
test_11.txt 13 ms 256 KB
test_12.txt 12 ms 256 KB
test_13.txt 14 ms 256 KB
test_14.txt 14 ms 256 KB
test_15.txt 10 ms 256 KB
test_16.txt 12 ms 256 KB
test_17.txt 14 ms 256 KB
test_18.txt 8 ms 256 KB
test_19.txt 8 ms 256 KB
test_20.txt 10 ms 256 KB
test_21.txt 32 ms 256 KB
test_22.txt 36 ms 256 KB
test_23.txt 34 ms 256 KB
test_24.txt 35 ms 256 KB
test_25.txt 34 ms 256 KB
test_26.txt 39 ms 256 KB
test_27.txt 34 ms 256 KB
test_28.txt 34 ms 256 KB
test_29.txt 34 ms 256 KB
test_30.txt 36 ms 256 KB