Submission #862879

#	Time	Username	Problem	Language	Result	Execution time	Memory
862879		iskhakkutbilim	Love Polygon (BOI18_polygon)	C++17	46 / 100	543 ms	39620 KiB

polygon

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

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1e5;

int n;
vector<string> a, b;
vector<string> compr;
map<string,int> compress;



vector<int> g[N+10];
int used[N + 10];
vector<int> G[N+10];
int idx[N+10];
vector<int> topo;
int num=1;

vector<int> sub[N+10];

void dfs(int v){
	used[v] = 1;
	for(int to : g[v]){
		if(!used[to]){
			dfs(to);
		}
	}
	topo.push_back(v);
}

void dfs2(int v){
	used[v] = 1;
	idx[v] = num;
	sub[num].push_back(v);
	for(int to : G[v]){
		if(!used[to]){
			dfs2(to);
		}
	}
}

main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n;
	a.resize(n);
	b.resize(n);
	for(int i = 0;i < n; i++){
		cin >> a[i] >> b[i];
		compr.push_back(a[i]);
	}
	sort(all(compr));
	int cnt1 = 1;
	for(auto x : compr){
		compress[x] = cnt1++;
	}
	for(int i = 0;i < n; i++){
		g[compress[a[i]]].push_back(compress[b[i]]);
		G[compress[b[i]]].push_back(compress[a[i]]);
	}
	if(n%2 == 1){
		cout << "-1";
		return 0;
	}
	if(n <= 20){
		vector<int> dp((1<<n), INT_MAX);
		dp[0] = 0;
		for(int mask = 0; mask < (1<<n); mask++){
			for(int i = 0;i < n; i++){
				for(int j = i + 1; j < n; j++){
					int new_mask = mask | (1<<i);
					new_mask|= (1<<j);
					int c = (g[i+1][0] != j + 1) + (g[j + 1][0] != (i + 1));
					dp[new_mask] = min(dp[new_mask], dp[mask] + c);
				}
			}
		}
		cout << dp[(1<<n)-1];
		return 0;
	}
	int ans = 0, self = 0;
	
	for(int i = 1;i <= n; i++){
		if(!used[i]){
			dfs(i);
		}
	}
	reverse(all(topo));
	for(int i = 1;i <= n; i++) used[i] = 0;
	for(int i : topo){
		if(!used[i]){
			dfs2(i);
			num++;
		}
	}
	for(int i = 1;i <= n; i++){
		int cnt = sub[i].size();
		if(cnt > 2){
			ans+= (cnt / 2);
			
		}
		self+= (cnt%2);
	}
	ans+= self;
	
	
	
	cout << ans;
	return 0;
}

Compilation message (stderr)

polygon.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      | ^~~~

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