제출 #862849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862849		maks007	Love Polygon (BOI18_polygon)	C++14	0 / 100	208 ms	31316 KiB

polygon

//Bismi Allah
#include "bits/stdc++.h"

using namespace std;

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	map <string,int> mp;
	vector <int> used(n, 0), rk(n, 0), g[n];
	function <void(int)> dfs=[&](int v) {
		used[v] = 1;
		rk[v] = 1;
		for(auto u : g[v]) {
			if(used[u]) continue;
			dfs(u);
			rk[v] += rk[u];	
		}
	};
	for(int i = 0; i < n; i ++) {
		string u, v;
		cin >> u >> v;
		if(mp.count(u) == 0) mp[u] = mp.size();
		if(mp.count(v) == 0) mp[v] = mp.size();
		g[mp[u]].push_back(mp[v]);
		g[mp[v]].push_back(mp[u]);
	}
	if(n % 2 == 1) {
		assert(false);
		cout << -1;
		return 0;
	}
	int ans = 0, mod = 0;
	for(int i = 0; i < n; i ++) {
		if(used[i]) continue;
		dfs(i);
		if(rk[i] == 2) continue;
		ans += rk[i] / 2;
		mod += (rk[i] % 2);
	}
	if(mod % 2 == 1) assert(false);
	else cout << ans + mod;
	return 0;
}

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