Submission #862852

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
862852	2023-10-19T06:22:21 Z	maks007	Love Polygon (BOI18_polygon)	C++14	29 / 100	257 ms	22356 KB

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), dp(n, 0), g[n], unite(n, 0);
	function <void(int,int)> dfs=[&](int v, int p) {
		used[v] = 1;
		for(auto u : g[v]) {
			if(used[u]) continue;
			dfs(u, v);
		}
		if(unite[v]) return;
		if(p != -1 && unite[p] == 0) {
			unite[p] = 1;
			unite[v] = 1;
		}
	};
	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();
		if(mp[u] == mp[v]) continue;
		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, -1);
	}
	for(auto i : unite) {
		ans += (i == 1);
		mod += (i == 0);
	}
	cout << ans/2+mod;
	return 0;
}

Subtask #1

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	564 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Incorrect	0 ms	344 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Incorrect	0 ms	344 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3

29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	257 ms	14936 KB	Output is correct
2	Correct	237 ms	18696 KB	Output is correct
3	Correct	128 ms	13880 KB	Output is correct
4	Correct	236 ms	17184 KB	Output is correct
5	Correct	241 ms	22356 KB	Output is correct
6	Correct	241 ms	17092 KB	Output is correct
7	Correct	251 ms	16980 KB	Output is correct
8	Correct	221 ms	16208 KB	Output is correct
9	Correct	215 ms	17376 KB	Output is correct
10	Correct	159 ms	17396 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	564 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Incorrect	0 ms	344 KB	Output isn't correct
9	Halted	0 ms	0 KB	-