Submission #1108540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108540		_rain_	Love Polygon (BOI18_polygon)	C++14	75 / 100	145 ms	147652 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);
	}
	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];
	}
	assert(nen.size()==n);
	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);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from polygon.cpp:1:
polygon.cpp: In function 'int32_t main()':
polygon.cpp:73:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |  assert(nen.size()==n);
      |         ~~~~~~~~~~^~~

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