Submission #862834

#	Time	Username	Problem	Language	Result	Execution time	Memory
862834		iskhakkutbilim	Love Polygon (BOI18_polygon)	C++17	0 / 100	144 ms	23784 KiB

polygon

#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 (stderr)

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

• Subtask 1: 0 / 21
• Subtask 2: 0 / 25
• Subtask 3: 0 / 29
• Subtask 4: 0 / 25