oj.uz

답안 #862834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862834 2023-10-19T05:39:11 Z iskhakkutbilim Love Polygon (BOI18_polygon) C++17
0 / 100
 144 ms 23784 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1e5;

int n;
vector<string> a, b;
vector<string> compr;
map<string,int> compress;
vector<int> g[N+10];
int used[N + 10];

int cnt, loves;
void dfs(int v){
	used[v] = 1;
	cnt++;
	for(int to : g[v]){
		if(used[to] == 0){
			dfs(to);
		}else if(used[to] == 1){
			loves++;
		}
	}
	used[v] = 2;
}


main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n;
	a.resize(n);
	b.resize(n);
	for(int i = 0;i < n; i++){
		cin >> a[i] >> b[i];
		compr.push_back(a[i]);
	}
	sort(all(compr));
	int cnt1 = 1;
	for(auto x : compr){
		compress[x] = cnt1++;
	}
	for(int i = 0;i < n; i++){
		g[compress[a[i]]].push_back(compress[b[i]]);
	}
//	for(int i = 0;i < n; i++){
//		cout << compress[a[i]] << " " << compress[b[i]] << '\n';
//	}
	if(n%2 == 1){
		cout << "-1";
		return 0;
	}
	int ans = 0, self = 0;
	for(int i = 1;i <= n; i++){
		if(!used[i]){
			cnt = 0, loves = 0;
			dfs(i);
			if(cnt > 2) ans = ans + (cnt / 2);
			self = self + (cnt % 2);
		}
	}
	if(self % 2 == 1) assert(false);
	ans+= (self * 2);
	cout << ans;
	return 0;
}

Compilation message

polygon.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      | ^~~~

Subtask #1
0 / 21.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 25.0

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