Submission #862876

#	Time	Username	Problem	Language	Result	Execution time	Memory
862876		iskhakkutbilim	Love Polygon (BOI18_polygon)	C++17	46 / 100	539 ms	29272 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];
 
int cnt, loves;
void dfs(int v){
	used[v] = 1;
	cnt++;
	for(int to : g[v]){
		if(used[to] == 0){
			dfs(to);
		}else if(used[to] == 1){
			loves++;
		}
	}
	used[v] = 2;
}
 
 
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]]);
	}
	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]){
			cnt = 0;
			dfs(i);
			if(cnt > 2) ans = ans + (cnt / 2);
			self = self + (cnt % 2);
		}
	}
	ans+= self;
	cout << ans;
	return 0;
}

Compilation message (stderr)

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

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