Submission #759471

#	Time	Username	Problem	Language	Result	Execution time	Memory
759471		MetalPower	Love Polygon (BOI18_polygon)	C++14	25 / 100	150 ms	10968 KiB

polygon

#include <bits/stdc++.h>
using namespace std;

const int MX = 2e5 + 10;

struct dsu{
	int p[MX], cc[MX];

	void init(){
		for(int i = 0; i < MX; i++) p[i] = i, cc[i] = 1;
	}

	int f(int x){
		if(p[x] == x) return x;
		else return p[x] = f(p[x]);
	}

	void Join(int u, int v){
		int fu = f(u), fv = f(v);
		if(fu == fv) return;
		p[fu] = fv;
		cc[fv] += cc[fu];
	}
} D;

int N, a[MX], b[MX], nx[MX], tim = 0;
map<string, int> mp;

bool dead[MX];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int ans = 0;

	cin >> N;
	for(int i = 0; i < N; i++){
		string s, t; cin >> s >> t;
		if(!mp.count(s)) mp[s] = ++tim;
		if(!mp.count(t)) mp[t] = ++tim;
		a[i] = mp[s], b[i] = mp[t];
		nx[a[i]] = b[i];
	}

	if(N % 2 == 1){
		cout << -1 << '\n';
		return 0;
	}

	for(int i = 1; i <= N; i++){
		if(nx[i] == i){
			dead[i] = true;
			ans++;
			continue;
		}
		if(!dead[i] && !dead[nx[i]] && nx[nx[i]] == i){
			dead[i] = true;
			dead[nx[i]] = true;
		}
	}

	D.init();
	for(int i = 1; i <= N; i++){
		if(!dead[i] && !dead[nx[i]]) D.Join(i, nx[i]);
	}

	for(int i = 1; i <= N; i++){
		if(dead[i]) continue;
		if(D.f(i) == i){
			int curr = D.cc[i];
			ans += (curr + 1) / 2;
		}
	}
	cout << ans << '\n';
}

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