Submission #1108687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108687		_rain_	Love Polygon (BOI18_polygon)	C++14	100 / 100	155 ms	37620 KiB

polygon

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define name "main"
 
const int N=(int)1e5;
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,int ban){
	if (ke[u].size()==0){
		dp[u][0]=0;
		dp[u][1]=1;
		return;
	}
	dp[u][0]=dp[u][1]=0;
	for(auto&v:ke[u]){
		if (v==ban) continue;
		dfs(v,ban);
		dp[u][1]+=dp[v][0];
	}
	dp[u][1]++;
	for(auto&v:ke[u]){
		if (v==ban) continue;
		dp[u][0]=max(dp[u][0],dp[u][1]-1+max(0,dp[v][1]-dp[v][0]));
	}
}
 
int tinhdfs(int u){
	if (bag[u].size()==1){
		dfs(bag[u][0],-1);
		return dp[bag[u][0]][0];
	}
	if (bag[u].size()==2){
		int ans=2;
		int x1=bag[u][0],x2=bag[u][1];
		for(auto&x:ke[x1]) {
			if (x==x2) continue;
			dfs(x,-1);
			ans+=dp[x][0];
		}
		for(auto&x:ke[x2]){
			if (x==x1) continue;
			dfs(x,-1);
			ans+=dp[x][0];
		}
		return ans;
	}
	int w1=1;
	int nn=bag[u][0],tv=to[nn];
	for(auto&v:ke[nn]){
		dfs(v,tv);
		w1+=dp[v][0];
	}
	for(auto&v:ke[tv]){
		if (v==nn) continue;
		dfs(v,nn);
		w1+=dp[v][0];
	}
	dfs(nn,nn);
	int w2=dp[nn][0];
	return max(w1,w2);
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n;
	if (n%2==1){
		cout<<-1;
		exit(0);
	}
	for(int i=1;i<=n;++i){
		cin>>s1[i]>>s2[i];
		nen.push_back(s1[i]);
		nen.push_back(s2[i]);
	}
	sort(nen.begin(),nen.end());
	nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	for(int i=1;i<=n;++i){
		u[i]=upper_bound(nen.begin(),nen.end(),s1[i])-nen.begin();
		v[i]=upper_bound(nen.begin(),nen.end(),s2[i])-nen.begin();
		to[u[i]]=v[i];
		if (v[i]!=u[i]) ke[v[i]].push_back(u[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) ++deg[i];
	}
	int ans=0;
	for(int i=1;i<=scc;++i){
		if (deg[i]==0){
			ans+=tinhdfs(i);
		}
	}
	cout<<n-ans;
	exit(0);
}

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