Submission #689995

#	Time	Username	Problem	Language	Result	Execution time	Memory
689995		NK_	Love Polygon (BOI18_polygon)	C++17	100 / 100	253 ms	21756 KiB

polygon

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using str = string;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	map<str, int> IDX;

	int cur = 0;
	auto idx = [&](const str& S) {
		if (IDX.find(S) != IDX.end()) return IDX[S];
		return IDX[S] = cur++;
	};

	int N; cin >> N;

	vector<int> P(N, -1), in(N);
	vector<vector<int>> chd(N);
	for(int i = 0; i < N; i++) {
		str S, T; cin >> S >> T;
		int s = idx(S), t = idx(T);

		P[s] = t; in[t]++;
		chd[t].push_back(s);
	}

	int left = 0, pairs = 0;
	queue<int> q; for(int i = 0; i < N; i++) if (in[i] == 0) q.push(i);

	set<int> cyc; for(int i = 0; i < N; i++) cyc.insert(i);

	while(int(size(q)) > 0) {
		int u = q.front(); q.pop();

		cyc.erase(u); 

		int v = P[u];
		if (v == -1) { left++; continue; }

		// check if already in relationship
		int x = P[v];
		if (x != -1 && x != v && P[x] == v) { left++; continue; }

		cyc.erase(v);

		for(auto x : chd[v]) {
			P[x] = -1;
		}

		if (P[v] != -1) {
			in[P[v]]--; if (in[P[v]] == 0) q.push(P[v]);
		}

		pairs++;
	}


	vector<int> vis(N);
	for(auto i : cyc) if (!vis[i]) {
		int u = i, len = 0;
		while(!vis[u]) {
			vis[u] = 1;
			u = P[u]; len++;
		} 
		if (len == 2) continue;
		left += len & 1; pairs += len / 2;
	}

	if (left % 2) cout << -1 << nl;
	else cout << left + pairs << nl;
    return 0;
}

/*
3
rocky scarlet 
scarlet patrick 
patrick rocky

8
leonard emmy 
ada emmy
isaac leonard 
emmy pierre 
pierre bernhard 
bernhard emmy 
sofia karl
karl sofia

4
a c
b c
c d
d d

*/

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