Submission #314153

#	Time	Username	Problem	Language	Result	Execution time	Memory
314153		Temmie	Love Polygon (BOI18_polygon)	C++17	100 / 100	290 ms	11516 KiB

polygon

#include <bits/stdc++.h>

std::vector <int> lv;
std::vector <bool> vis;

int dfs(int node) {
	vis[node] = true;
	return (vis[lv[node]] ? 1 : dfs(lv[node]) + 1);
}

int main() {
	std::ios::sync_with_stdio(0);
	
	int n; std::cin >> n;
	std::map <std::string, int> mp;
	std::string s, t;
	int m = 1, ans = 0;
	std::vector <int> ld(n + 1, 0);
	lv.resize(n + 1, 0);
	vis.resize(n + 1, false);
	for (int i = 0; i < n; i++) {
		std::cin >> s >> t;
		if (!mp[s]) mp[s] = m++;
		if (!mp[t]) mp[t] = m++;
		lv[mp[s]] = mp[t];
		ld[mp[t]]++;
	}
	if (n & 1) {
		std::cout << "-1\n";
		return 0;
	}
	std::queue <int> q;
	for (int i = 0; i < n; i++) {
		if (i + 1 == lv[lv[i + 1]] && lv[i + 1] != i + 1) {
			vis[i + 1] = true;
			vis[lv[i + 1]] = true;
		} else if (!ld[i + 1]) q.push(i + 1);
	}
	while (q.size()) {
		int now = q.front(); q.pop();
		vis[now] = true;
		if (!vis[lv[now]]) {
			vis[lv[now]] = true;
			if (!--ld[lv[lv[now]]]) q.push(lv[lv[now]]);
		}
		ans++;
	}
	for (int i = 0; i < n; i++)
		if (!vis[i + 1]) ans += (dfs(i + 1) + 1) >> 1;
	std::cout << ans << "\n";
	std::cin >> n;
	
}
























































































































































































// imagine there's no heaven

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