Submission #704708

#	Time	Username	Problem	Language	Result	Execution time	Memory
704708		pakapu	Love Polygon (BOI18_polygon)	C++17	0 / 100	1232 ms	11252 KiB

polygon

#include <bits/stdc++.h>

using namespace std;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	int ans = 0;
	int cnt = 0;
	vector<int> loves(n);
	map<string, int> mp;

	for(int i = 0; i < n; i++) {
		string f, s;
		cin >> f >> s;

		if(mp.find(f) == mp.end()) {
			mp[f] = cnt;
			cnt++;
		}
		if(mp.find(s) == mp.end()) {
			mp[s] = cnt;
			cnt++;
		}

		loves[mp[f]] = mp[s];
	}

	/*for(auto c : loves) {
		cout << c << ' ';
	}
	cout << '\n';*/

	if(n % 2 == 0) {
		vector<int> ok(n);

		for(int i = 0; i < n; i++) {
			if(loves[loves[i]] == i && loves[i] != i) {
				ok[i] = true;
				ok[loves[i]] = true;
			}
		}

		/*for(auto c : ok) {
			cout << c << ' ';
		}
		cout << '\n';*/

		for(int i = 0; i < n; i++) {
			//cout << i << " is not ok at the moment!\n";
			if(!ok[i]) {
				if(!ok[loves[i]] && loves[i] != i) {
					cout << i << '\n';
					loves[loves[i]] = i;
					ans++;
					ok[i] = true;
					ok[loves[i]] = true;
					continue;
				}

				int loves_curr = -1;
				for(int j = 0; j < n; j++) {
					if(loves[j] == i && loves[j] != i && j != i) {
						loves_curr = j;
						break;
					}
				}

				if(loves_curr == -1) {
					int first_not_ok = -1;
					for(int j = 0; j < n; j++) {
						if(!ok[j] && j != i) {
							first_not_ok = j;
							break;
						}
					}

					loves[i] = first_not_ok;
					loves[first_not_ok] = i;
					ans += 2;
					ok[i] = true;
					ok[first_not_ok] = true;
				}
				else {
					loves[i] = loves_curr;
					ans++;
					ok[i] = true;
					ok[loves_curr] = true;
				}
			}
		}
		/*for(auto c : ok) {
			cout << c << ' ';
		}
		cout << '\n';*/
	}
	else {
		ans = -1;
	}
	
	/*for(auto c : loves) {
		cout << c << ' ';
	}
	cout << '\n';*/

	cout << ans << '\n';

	return 0;
}

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