Submission #1127686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127686		nguyenphong233	Love Polygon (BOI18_polygon)	C++20	100 / 100	169 ms	9416 KiB

polygon

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)1e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n;
map<string,int> mp;
int id,adj[MAX],deg[MAX];
bool del[MAX];

signed main(){
	
	read();
	cin >> n;
	id = 0;
	for(int i = 1,u,v;i <= n;i++){
		string s,t;
		cin >> s >> t;
		if(!mp.count(s))mp[s] = ++id;
		if(!mp.count(t))mp[t] = ++id;
		adj[mp[s]] = (mp[t]);
		deg[mp[t]]++;
	}
	if(id & 1)return cout << "-1",0;
	
	deque<int> h;
	for(int i = 1;i <= id;i++){
		if(adj[adj[i]] == i && i != adj[i]){
			del[i] = 1;
			del[adj[i]] = 1;
		}
		if(deg[i] == 0)h.push_back(i);
	}

	int res = 0;
	while(!h.empty()){
		int u = h.front();
		h.pop_front();
		if(del[u])continue;
		del[u] = 1;
		int v = adj[u];
		res++;
		if(!del[v]){
			del[v] = 1;
			int w = adj[v];
			deg[w]--;
			if(deg[w] == 0)h.push_back(w);
		}
	}
	//cout << res << '\n';
	for(int i = 1;i <= n;i++){
		if(del[i])continue;
		del[i] = 1;
		int cnt = 1;
		int u = adj[i];
		while(u != i){
			cnt++;
			del[u] = 1;
			u = adj[u];
		}				
		res += (cnt + 1) >> 1;									
	}
	cout << res << "\n";
	
	
}

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