Submission #488113

#	Time	Username	Problem	Language	Result	Execution time	Memory
488113		MohamedAhmed04	Love Polygon (BOI18_polygon)	C++14	100 / 100	273 ms	12604 KiB

polygon

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int n ;

string s1 , s2 ;

map<string , int>mp ;

int id = 0 ;

int indeg[MAX] , to[MAX] ;
int match[MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
	{
		cin>>s1>>s2 ;
		if(mp.find(s1) == mp.end())
			mp[s1] = ++id ;
		if(mp.find(s2) == mp.end())
			mp[s2] = ++id ;
		if(s2 != s1)
			indeg[mp[s2]]++ ;
		to[mp[s1]] = mp[s2] ;
	}
	if(n&1)
		return cout<<-1<<"\n" , 0 ;
	priority_queue< pair<int , int> , vector< pair<int , int> > , greater< pair<int , int> > >q ;
	for(int i = 1 ; i <= n ; ++i)
	{
		q.push({indeg[i] , i}) ;
		if(to[i] != i && to[to[i]] == i)
			match[i] = 1 , match[to[i]] = 1 ;
	}
	int ans = 0 ;
	while(!q.empty())
	{
		pair<int , int>p = q.top() ;
		q.pop() ;
		int node = p.second ;
		if(match[node])
			continue ;
		ans++ ;
		match[node] = 1 ;
		int x = to[node] ;
		if(match[x])
			continue ;
		match[x] = 1 ;
		indeg[to[x]]-- ;
		q.push({indeg[to[x]] , to[x]}) ;
	}
	return cout<<ans<<"\n" , 0 ;
}		

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