Submission #1129674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129674		Muhammet	Love Polygon (BOI18_polygon)	C++20	100 / 100	200 ms	14140 KiB

polygon

#include "bits/stdc++.h"

using namespace std;

#define SZ(s) (int)s.size()
#define ss second
#define ff first

const int N = 1e5+5;

map <string, int> mp;

vector <int> p, cn, vis;

int n, k, ans;

void dfs(int x){
	vis[x] = true;
	int y = p[x];
	if(y == x or vis[y]){
		ans++;
		return;
	}
	vis[y] = true;
	if(p[y] == x) return;
	ans++;
	if(!vis[p[y]]) dfs(p[y]);
}

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n;
	int cnt = 0;
	p.assign(n+1, 0), cn.assign(n+1,0);
	for(int i = 0; i < n; i++){
		string s, t;
		cin >> s >> t;
		if(mp.find(s) == mp.end()){
			mp[s] = (++cnt);
		}
		if(mp.find(t) == mp.end()){
			mp[t] = (++cnt);
		}
		p[mp[s]] = mp[t];
		cn[mp[t]]++;
	}
	if(n % 2 == 1) {
		cout << -1;
		return 0;
	}
	vis.assign(n+1,0);
	set <pair<int,int>> s;
	for(int i = 1; i <= n; i++){
		int y = p[i];
		if(p[y] == i and y != i) vis[i] = vis[y] = true;
	}
	for(int i = 1; i <= n; i++){
		if(vis[i]) continue;
		s.insert({cn[i], i});
	}
	while(SZ(s)){
		auto [z, x] = *s.begin();
		if(z) break;
		int y = p[x];
		s.erase(s.begin());
		vis[x] = true;
		if(vis[y] or y == x){
			ans++;
			continue;
		}
		ans++;
		s.erase(s.find({cn[y],y}));
		vis[y] = true;
		if(p[y] == y or vis[p[y]]) continue;
		s.erase(s.find({cn[p[y]],p[y]}));
		cn[p[y]]--;
		s.insert({cn[p[y]],p[y]});
	}
	for(int i = 1; i <= n; i++){
		if(vis[i]) continue;
		dfs(i);
	}
	cout << ans;
	return 0;
}

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