Submission #718109

#	Time	Username	Problem	Language	Result	Execution time	Memory
718109		amirhoseinfar1385	Love Polygon (BOI18_polygon)	C++17	21 / 100	121 ms	15284 KiB

polygon

#include<bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	map<string,int>mp;
	vector<pair<string,string>>all(n);
	for(int i=0;i<n;i++){
		cin>>all[i].first>>all[i].second;
		mp[all[i].first]=i;
	}
	vector<int>adj(n+1);
	for(int i=0;i<n;i++){
		adj[i]=mp[all[i].second];
	}
	if(n&1){
		cout<<-1<<"\n";
		return 0;
	}
	if(n<=20){
	int res=n;
	for(int i=0;i<(1<<n);i++){
		int f=1,cnt=0;
		vector<int>cnta(n+1);
		for(int j=0;j<n;j++){
			if((i>>j)&1){
				continue;
			}
			if((i>>(adj[j]))&1){
				cnt++;
				cnta[adj[j]]++;
				if(cnta[adj[j]]>1){
					f=0;
				}
				continue;
			}
			if(adj[adj[j]]!=j||adj[j]==j){
				f=0;
			}
		}
		if(f&&cnt<=__builtin_popcount(i)){
			//cout<<i<<" "<<cnt<<" "<<f<<'\n';
			res=min(res,__builtin_popcount(i));
		}
	}
	cout<<res<<"\n";
	return 0;
	}
	int res=0;
	vector<int>vis(n+1);
	for(int i=1;i<=n;i++){
		if(vis[i]==0){
			int cnt=0;
			int fi=i;
			while(vis[fi]==0){
				vis[fi]=1;
				cnt++;
				fi=adj[fi];
			}
			if(cnt==2){
				continue;
			}
			res+=(cnt+1)/2;
		}
	}
	cout<<res<<"\n";
}

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