Submission #314034

#	Time	Username	Problem	Language	Result	Execution time	Memory
314034		sofapuden	Love Polygon (BOI18_polygon)	C++14	100 / 100	416 ms	17880 KiB

polygon

#include <bits/stdc++.h>

using namespace std;

int main(){
	int n, ans = 0; cin >> n;
	vector<pair<string,string>> in;
	vector<int> belove(n), love(n);
	
	map<string,int> M;
	
	queue<int> nobody;
	
	vector<bool> vis(n,false);
	
	if(n & 1){
		cout << "-1\n"; return 0;
	}
	
	for(int i = 0; i < n; ++i){
		string s1, s2; cin >> s1 >> s2;
		M[s1] = i;
		in.push_back({s1,s2});
	}
	for(int i = 0; i < n; ++i){
		love[M[in[i].first]] = M[in[i].second];
		belove[M[in[i].second]]++;
	}
	for(int i = 0; i < n; ++i){
		if(love[love[i]] == i && love[i] != i)vis[i] = true;
		if(!belove[i]){nobody.push(i);}
	}
	while(!nobody.empty()){
		auto x = nobody.front();
		nobody.pop();
		vis[x] = true;
		if(!vis[love[x]]){
			vis[love[x]] = true;
			if(--belove[love[love[x]]] == 0)nobody.push(love[love[x]]);
		}
		ans++;
	}
	for(int i = 0; i < n; ++i){
		if(!vis[i]){
			vis[i] = true;
			int last = i;
			vis[last] = true;
			int cnt = 1;
			while(!vis[love[last]]){
				cnt++;
				last = love[last];
				vis[last] = true;
			}
			ans+=(cnt+1)>>1;
		}
	}
	cout << ans << "\n";
}

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