oj.uz

Submission #716527

# Submission time Handle Problem Language Result Execution time Memory
716527 2023-03-30T08:58:26 Z ajab_01 Love Polygon (BOI18_polygon) C++17
54 / 100
 311 ms 27320 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<int> g[N] , adj[N] , cy;
map<string , int> mp;
int ans , n , num , len , cnt;
bool deg[N] , vis[N] , make_rel[N] , ch = 1;

void dfs(int ver){
	vis[ver] = 1;
	len++;
	for(int i : g[ver]){
		if(vis[i]) continue;
		dfs(i);
	}
}

void dfs2(int ver){
	vis[ver] = 1;
	for(int i : adj[ver]){
		if(vis[i]) continue;
		dfs2(i);
		if(!make_rel[i] && !make_rel[ver]) make_rel[i] = make_rel[ver] = 1;
	}
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 0 ; i < n ; i++){
		string a , b;
		cin >> a >> b;
		if(mp.find(a) == mp.end()) mp[a] = num++;
		if(mp.find(b) == mp.end()) mp[b] = num++;
		g[mp[a]].push_back(mp[b]);
		adj[mp[b]].push_back(mp[a]);
		deg[mp[b]] = 1;
	}
	if(n & 1){
		cout << -1 << '\n';
		return 0;
	}

	for(int i = 0 ; i < n ; i++)
		ch &= deg[i];

	if(ch){
		for(int i = 0 ; i < n ; i++){
			if(vis[i]) continue;
			len = 0;
			dfs(i);
			if(len == 2) continue;
			ans += len / 2;
			if(len & 1) ans++;
		}
		cout << ans << '\n';
		return 0;
	}

	for(int i = 0 ; i < n ; i++)
		if(g[i][0] == i)
			dfs2(i);
	for(int i = 0 ; i < n ; i++)
		if(make_rel[i])
			cnt++;
	ans = n - cnt;
	ans += cnt / 2;
	cout << ans << '\n';
	return 0;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4960 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 301 ms 22012 KB Output is correct
5 Correct 304 ms 19180 KB Output is correct
6 Correct 306 ms 22396 KB Output is correct
7 Correct 273 ms 19148 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 18516 KB Output is correct
2 Correct 304 ms 22480 KB Output is correct
3 Correct 230 ms 21436 KB Output is correct
4 Correct 267 ms 19780 KB Output is correct
5 Correct 311 ms 27320 KB Output is correct
6 Correct 305 ms 19936 KB Output is correct
7 Correct 287 ms 20020 KB Output is correct
8 Correct 259 ms 20284 KB Output is correct
9 Correct 266 ms 19656 KB Output is correct
10 Correct 198 ms 18588 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4960 KB Output isn't correct
5 Halted 0 ms 0 KB -