oj.uz

답안 #716506

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
716506 2023-03-30T08:07:13 Z ajab_01 Love Polygon (BOI18_polygon) C++17
0 / 100
 223 ms 13712 KB 
#include<bits/stdc++.h>
using namespace std;

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

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]);
		deg[mp[b]] = 1;
	}
	if(n & 1){
		cout << -1 << '\n';
		return 0;
	}

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

	if(ch){
		vector<int> vec;
		for(int i = 1 ; i <= n ; i++){
			int len = 0 , ver = i;
			while(!vis[ver]){
				len++;
				vis[ver] = 1;
				ver = g[ver][0];
			}
			if(len == 2) continue;
			vec.push_back(len);
		}

		int cnt = 0;
		for(int i : vec){
			ans += i / 2;
			if(i & 1) cnt++;
		}
		ans += cnt - 1;
		cout << ans << '\n';
	}
	return 0;
}

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 223 ms 13712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -