Submission #1191128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191128		Abdalaziz_Alshami	Love Polygon (BOI18_polygon)	C++20	0 / 100	179 ms	428 KiB

polygon

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=22;
int a[N],vis[N],ssz[N],sz[N];
signed main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int n; cin>>n;
	map<string,int>m; 
	int d=1;
	for(int i=0;i<n;i++){
		string u,v; cin>>u>>v; 
		if(!m[u]) m[u]=d++;
		if(!m[v]) m[v]=d++;
		a[m[u]-1]=m[v]-1;
		ssz[m[v]-1]++;
	}
	if(n%2) { cout<<-1; return 0; }
	int ans=1e18;
	for(int i=0;i<(1<<n);i++){
		memset(vis,0,sizeof vis);
		int ss=0;
		bool f=true;
		for(int i=0;i<n;i++) sz[i]=ssz[i];
		for(int j=0;j<n;j++){
			if((i>>j)&1) vis[j]=1,sz[a[j]]--,ss++;
			else if(a[j]==j) f=false;
		}
		if(!f) continue;
		queue<int>q;
		int g=0;
		for(int i=0;i<n;i++){ 
			if(!vis[i]&&sz[i]==0) q.push(i);
			if(a[a[i]]==i) g++;
		}
		while(q.size()){
			int x=q.front(); q.pop();
			if(!vis[x]){
				if(!vis[a[x]]){
					vis[x]=1; vis[a[x]]=1; 
					if(!vis[a[a[x]]]) q.push(a[a[x]]);					
				}
			}
		}
		for(int i=0;i<n;i++){
			if(!vis[i]){
				int s=1,j=i; vis[i]=1;
				while(!vis[a[j]]) j=a[j],s++,vis[j]=1;
				if(s%2) f=false;
			}
		}
		if(!f) continue; 
		ans=min(ans,ss+(n-ss)/2-g/2);
	}
	if(ans==1e18) cout<<-1; 
	else cout<<ans;
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 25
• Subtask 3: 0 / 29
• Subtask 4: 0 / 25