Submission #314026

#	Time	Username	Problem	Language	Result	Execution time	Memory
314026		sofapuden	Love Polygon (BOI18_polygon)	C++14	0 / 100	546 ms	24660 KiB

polygon

#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
	int n, ans = 0; cin >> n;
	vector<pair<string,string>> in;
	vector<vector<int>> belove(n);
	vector<int> love(n);
	vector<int> cn(n);
	
	map<string,int> M;
	set<int> iR;
	
	queue<int> nobody;
	queue<int> sad;
	
	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];
		if(in[i].first != in[i].second)belove[M[in[i].second]].push_back(M[in[i].first]);
	}
	for(int i = 0; i < n; ++i){
		if(love[love[i]] == i && love[i] != i)iR.insert(i);
		if(love[i] == i){iR.insert(i);ans++;}
		cn[i] = belove[i].size();
		if(cn[i] == 0)sad.push(i);
	}
	for(int i = 0; i < n; ++i){
		if(love[i] == i || (iR.count(love[i]) && !iR.count(i)))nobody.push(i);
	}
	while(!nobody.empty() || !sad.empty()){
		while(!nobody.empty()){
			auto x = nobody.front();
			nobody.pop();
			if(iR.count(x))continue;
			if(belove[x].size()){
				iR.insert(x);
				iR.insert(belove[x][0]);
				ans++;
				for(int i = 0; i < (int)belove[x].size(); ++i){
					if(!iR.count(belove[x][i]))nobody.push(belove[x][i]);
				}
			}
		}
		if(!sad.empty()){
			auto x = sad.front();
			sad.pop();
			if(iR.count(x)){continue;}
			if(iR.count(love[x])){ans++; iR.insert(x); continue;}
			iR.insert(x);
			iR.insert(love[x]);
			ans++;
			for(int i = 0; i < (int)belove[love[x]].size(); ++i){
				if(!iR.count(belove[love[x]][i]))nobody.push(belove[love[x]][i]);
			}
			cn[love[love[x]]]--;
			if(!cn[love[love[x]]]){
				sad.push(love[love[x]]);
			}
		}
	}
	for(int i = 0; i < n; ++i){
		if(!vis[i] && !iR.count(i)){
			int last = i;
			vis[last] = true;
			int cnt = 2;
			while(love[last] != i){
				cnt++;
				last = love[last];
				vis[last] = true;
			}
			ans+=(cnt+1)>>1;
		}
	}
	cout << ans << "\n";
}

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