Submission #862882

#	Time	Username	Problem	Language	Result	Execution time	Memory
862882		iskhakkutbilim	Love Polygon (BOI18_polygon)	C++17	75 / 100	259 ms	47056 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);
		}
	}
}
int ans;
vector<int> cond[N+10];
int taken[N + 10];
void dfs3(int v, int par){
	used[v] = 1;
	for(int to : cond[v]){
		if(used[to]) continue;
		dfs3(to, v);
	}
	if(par != -1 && !taken[par] && !taken[v]){
//		cout << v << " " << par << '\n';
		taken[v] = taken[par] = 1;
		ans++;
	}
}


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++){
//		cout << a[i] << " = " << compress[a[i]] << '\n';
//	}
	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;
//	}
	
	
	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);
		}
		if(cnt % 2 == 0){
			taken[i] = 1;
		}
	}
	
	for(int i = 1;i <= n; i++){
		set<int> st;
		for(int to : g[i]){
			if(idx[i] != idx[to]){
				st.insert(idx[to]);
			}
		}
		for(int u : st){
			cond[idx[i]].push_back(u);
			cond[u].push_back(idx[i]);
		}
	}
//	for(int i = 1;i < num; i++){
//		cout << i << " = ";
//		for(int x : sub[i]){
//			cout << x << ' ';
//		}
//		cout << '\n';
//	}
	for(int i = 1;i <= n; i++){
		used[i] = 0;
	}
	
	for(int i = 1;i < num; i++){
		if(!used[i]){
			dfs3(i, -1);
		}
	}
	for(int i = 1;i < num; i++){
		if(taken[i] != 1) ans++;
	}
	
	
	cout << ans;
	return 0;
}

Compilation message (stderr)

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

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