oj.uz

Submission #862862

# Submission time Handle Problem Language Result Execution time Memory
862862 2023-10-19T06:57:56 Z maks007 Love Polygon (BOI18_polygon) C++14
54 / 100
 286 ms 25036 KB 
//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), loved(n, 0), rk(n, 0);
	function <void(int,int)> dfs=[&](int v, int p) {
		used[v] = 1;
		rk[v] = 1;
		for(auto u : g[v]) {
			if(used[u]) continue;
			dfs(u, v);
			rk[v] += rk[u];
		}
		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();
		loved[mp[v]] ++;
		if(mp[u] == mp[v]) continue;
		g[mp[u]].push_back(mp[v]);
		g[mp[v]].push_back(mp[u]);
	}
	if(*min_element(loved.begin(), loved.end()) >= 1) {
		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);
			if(rk[i] == 2) continue;
			ans += rk[i] / 2;
			mod += (rk[i] % 2);
		}
		if(mod % 2 == 1) cout << -1;
		else cout << ans + mod;
		return 0;
	}
	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 600 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 268 ms 23636 KB Output is correct
5 Correct 277 ms 15440 KB Output is correct
6 Correct 275 ms 25036 KB Output is correct
7 Correct 264 ms 15668 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 15700 KB Output is correct
2 Correct 260 ms 17236 KB Output is correct
3 Correct 135 ms 12416 KB Output is correct
4 Correct 249 ms 15700 KB Output is correct
5 Correct 286 ms 21332 KB Output is correct
6 Correct 252 ms 15700 KB Output is correct
7 Correct 263 ms 15720 KB Output is correct
8 Correct 197 ms 14868 KB Output is correct
9 Correct 270 ms 15860 KB Output is correct
10 Correct 170 ms 15884 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 1 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 600 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -