Submission #1108541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108541		_rain_	Love Polygon (BOI18_polygon)	C++14	75 / 100	173 ms	145920 KiB

polygon

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define name "main"
 
const int N=(int)1e6;
vector<string>nen;
string s1[N+2],s2[N+2];
int deg[N+2],num[N+2],low[N+2],id[N+2],scc=0,timedfs=0;
int u[N+2],v[N+2],to[N+2],dp[N+2][2],n;
vector<int>ord,bag[N+2],ke[N+2];
bool used[N+2],del[N+2];
 
void buildup(int u){
	num[u]=low[u]=++timedfs;
	ord.push_back(u);
	
	if (!num[to[u]]&&!del[to[u]]){
		buildup(to[u]);
		low[u]=min(low[u],low[to[u]]);
	}
	else if (!del[to[u]]) low[u]=min(low[u],num[to[u]]);
	if (low[u]==num[u]){
		int v;
		++scc;
		do{
			v=ord.back();
			ord.pop_back();
			id[v]=scc;
			del[v]=true;
			bag[id[v]].push_back(v);
		}while(v!=u);
	}
}
void dfs(int u){
	if (ke[u].size()==0){
		dp[u][0]=0;
		dp[u][1]=1;
		return;
	}
	for(auto&v:ke[u]){
		dfs(v);
		dp[u][1]+=dp[v][0];
	}
	dp[u][1]++;
	for(auto&v:ke[u]){
		dp[u][0]=max(dp[u][0],dp[u][1]-1+max(0,dp[v][1]-dp[v][0]));
	}
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n;
	if (n%2==1){
		cout<<-1;
		exit(0);
	}
	map<string,int> mp;
	int cn=0;
	for(int i=1;i<=n;++i){
		string s1,s2; cin>>s1>>s2;
		if (mp.find(s1)==mp.end()) mp[s1]=++cn;
		if (mp.find(s2)==mp.end()) mp[s2]=++cn;
		u[i]=mp[s1];
		v[i]=mp[s2];
		to[u[i]]=v[i];
	}
	for(int i=1;i<=n;++i) if (!num[i]) buildup(i);
	for(int i=1;i<=scc;++i){
		for(auto&u:bag[i]){
			if (id[to[u]]!=i){
				ke[id[to[u]]].push_back(i);
				deg[i]++;
			}
		}
	}
	for(int i=1;i<=scc;++i) {
		sort(ke[i].begin(),ke[i].end());
		ke[i].resize(unique(ke[i].begin(),ke[i].end())-ke[i].begin());
	}
	int ans=0;
	// for(int i=1;i<=n;++i){
	// 	cout<<u[i]<<' '<<v[i]<<'\n';
	// }
	// for(int i=1;i<=n;++i) cout<<id[i]<<' '; cout<<'\n';
	for(int i=1;i<=scc;++i){
		if (deg[i]==0){
			dfs(i);
			if (bag[i].size()==2) ans+=2; else ans+=bag[i].size()/2;
			if (bag[i].size()%2==0) ans+=dp[i][1]-1; else ans+=dp[i][0];
		}
	}
	cout<<n-ans;
	exit(0);
}

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