Submission #748458

#	Time	Username	Problem	Language	Result	Execution time	Memory
748458		mariowong	Love Polygon (BOI18_polygon)	C++14	100 / 100	449 ms	17160 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
 
map <string,pair<string,int>  > love;
string s[100005];
int in[100005];
bool ok[100005];
int main(){
    ios::sync_with_stdio(false);
    int n;	
    cin >> n;
    for (int i=1;i<=n;i++){
    	string t;
    	cin >> s[i] >> t;
    	love[s[i]]={t,i};
    }
    for (int i=1;i<=n;i++){
    	if (love[love[s[i]].first].first == s[i] && s[i] != love[s[i]].first) ok[i]=ok[love[love[s[i]].first].second]=true;
    	else in[love[love[s[i]].first].second]++;
    }
	int ans=0;
	for (int i=1;i<=n;i++){
		if (in[i] == 0 && !ok[i] && !ok[love[love[s[i]].first].second]){
			ans++,ok[i]=ok[love[love[s[i]].first].second]=true; 
			string now=love[love[s[i]].first].first;	
			in[love[now].second]--;
			while (in[love[now].second] == 0){
				if (now != love[now].first && !ok[love[now].second] && !ok[love[love[now].first].second]){
					ok[love[now].second]=ok[love[love[now].first].second]=true;
					ans++;
					now=love[love[now].first].first;
					in[love[now].second]--;
				}
				else
				break;
			}
		}
	}
	for (int i=1;i<=n;i++){
		if (s[i] != love[s[i]].first && !ok[i] && !ok[love[love[s[i]].first].second]){
			ans++,ok[i]=ok[love[love[s[i]].first].second]=true; 	
			string now=love[love[s[i]].first].first;
			in[love[now].second]--;
			while (in[love[now].second] == 0){
				if (now != love[now].first && !ok[love[now].second] && !ok[love[love[now].first].second]){
					ok[love[now].second]=ok[love[love[now].first].second]=true;
					ans++;
					now=love[love[now].first].first;
					in[love[now].second]--;
				}
				else
				break;
			}
		}
	}
	for (int i=1;i<=n;i++){
		if (!ok[i]) ans++;	
	}
    if (n%2 == 1) cout << "-1\n";
    else cout << ans << "\n";
	return 0;
}

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