Submission #792924

#	Time	Username	Problem	Language	Result	Execution time	Memory
792924		UmairAhmadMirza	Love Polygon (BOI18_polygon)	C++14	25 / 100	394 ms	29508 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
int const N=1e5+5;
map<string,int> mp;
int suc[N];
vector<int> lover[N];
vector<int> adj[N];
vector<int> cc[N];
int c=0;
int ccn[N];
void dfs(int node){
	ccn[node]=c;
	cc[c].push_back(node);
	for(auto i:adj[node])
		if(ccn[i]==0)
			dfs(i);

}
// int largest_independent_set(int n){
// 	return //;
// }
int main(){
	int n;
	cin>>n;
	string a,b;
	int sz=1;
	for (int i = 0; i < n; ++i)
	{
		cin>>a>>b;
		if(mp[a]==0){
			mp[a]=sz;
			sz++;
		}
		if(mp[b]==0){
			mp[b]=sz;
			sz++;
		}
		suc[mp[a]]=mp[b];
		lover[mp[b]].push_back(mp[a]);
		adj[mp[b]].push_back(mp[a]);
		adj[mp[a]].push_back(mp[b]);
	}
	if(n%2){
		cout<<-1<<endl;
		return 0;
	}
	for (int i = 1; i <=n; ++i)
		if(ccn[i]==0){
			c++;
			dfs(i);
		}
	int ans=0;
	for (int i = 1; i <=c; ++i)
	{
		int k=cc[i].size();
		if(k==2)
			continue;
		ans+=k/2;
		ans+=k%2;
	}
	cout<<ans<<endl;
	return 0;
}

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