Submission #1129485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129485		stdfloat	Love Polygon (BOI18_polygon)	C++20	0 / 100	133 ms	8536 KiB

polygon

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

using ll = long long;

#define sz(v)	(int)(v).size()

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;

	if (n & 1) return cout << -1, 0;

	vector<int> pr(n);
	map<string, int> m;
	for (int i = 0; i < n; i++) {
		string s, t;
		cin >> s >> t;

		if (m.find(s) == m.end()) m[s] = (int)m.size();
		if (m.find(t) == m.end()) m[t] = (int)m.size();
	
		pr[m[s]] = m[t];
	}

	int cnt = 0;
	vector<bool> vis(n);
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
	
		int x = i, cnt1 = 0;
		while (!vis[x]) {
			cnt1++;
			vis[x] = true;
			x = pr[x];
		}

		assert(x == i);

		cnt += (cnt1 & 1);
	}

	assert(!(cnt & 1));

	cout << (n >> 1) + (cnt >> 1);
}

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