Submission #793021

#	Time	Username	Problem	Language	Result	Execution time	Memory
793021		UmairAhmadMirza	Love Polygon (BOI18_polygon)	C++14	29 / 100	427 ms	29864 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];
int _dp[N],dp[N];
void dfs(int node){
	ccn[node]=c;
	cc[c].push_back(node);
	for(auto i:adj[node])
		if(ccn[i]==0)
			dfs(i);
}
void LIS(int root){//largest_independent_set
	// cout<<root<<endl;
	for(auto i:lover[root])
		if(i!=root)
			LIS(i);
	_dp[root]=1;
	int maxx=0;
	for(auto i:lover[root])
		if(i!=root){
			_dp[root]+=dp[i];
			dp[root]+=dp[i];
			maxx=max(maxx,_dp[i]-dp[i]);
		}
	dp[root]+=maxx;
}
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++;
		}
		// cout<<mp[a]<<' '<<mp[b]<<endl;
		suc[mp[a]]=mp[b];
		if(mp[a]==mp[b])
			continue;
		adj[mp[b]].push_back(mp[a]);
		adj[mp[a]].push_back(mp[b]);
		suc[mp[a]]=mp[b];
		lover[mp[b]].push_back(mp[a]);
	}
	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)
	{
		for(auto v:cc[i])
			if(suc[v]==v){
				LIS(v);
				ans+=dp[v];
			}
	}
	cout<<n-ans<<endl;
	// for (int i = 1; i <=n; ++i)
	// {
	// 	cout<<dp[i]<<' '<<_dp[i]<<endl;
	// }
	return 0;
}

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