Submission #759529

#	Time	Username	Problem	Language	Result	Execution time	Memory
759529		MetalPower	Love Polygon (BOI18_polygon)	C++14	100 / 100	178 ms	12680 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], degree[MX], vis[MX], tim = 0;
map<string, int> mp;

bool dead[MX];

int dfs(int x){
	if(vis[x]) return 0;
	vis[x] = true;
	return 1 + dfs(nx[x]);
}

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];
		degree[b[i]]++;
		if(nx[b[i]] == a[i] && a[i] != b[i]){
			vis[a[i]] = true;
			vis[b[i]] = true;
		}
	}

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

	vector<int> qsolve;
	for(int i = 1; i <= N; i++){
		if(degree[i] == 0) qsolve.push_back(i);
	}

	for(; !qsolve.empty(); ){
		int st = qsolve.back(); qsolve.pop_back();
		if(vis[st] || vis[nx[st]]) continue;
		ans++;
		vis[st] = 1;
		vis[nx[st]] = 1;
		degree[nx[st]]--;
		if(nx[nx[st]] == nx[st]) continue;
		degree[nx[nx[st]]]--;
		if(!vis[nx[nx[st]]] && degree[nx[nx[st]]] == 0) qsolve.push_back(nx[nx[st]]);
	}

	for(int i = 1; i <= N; i++){
		if(vis[i]) continue;
		int curr_sz = dfs(i);
		ans += (curr_sz + 1) / 2;
	}

	cout << ans << '\n';
}

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