Submission #949427

#	Time	Username	Problem	Language	Result	Execution time	Memory
949427		koukirocks	Love Polygon (BOI18_polygon)	C++17	0 / 100	814 ms	1048576 KiB

polygon

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
 
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=998244353;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
 
int n;
vector<pair<string,string> > eg;
int G[MAX];
vector<int> cptG[MAX];
int dp[MAX][2];

void dfs(int v,int p,vector<bool>& vis,vector<bool>& tmpvis,vector<int>& ccl,int& stt) {
	tmpvis[v]=true;
	for (int i:cptG[v]) {
		if (tmpvis[i]) {
			stt=i;
			ccl.push_back(v);
			if (i==v) stt=0;
			return;
		}
		if (i==p) continue;
		dfs(i,v,vis,tmpvis,ccl,stt);
		if (stt>=0) {
			if (stt>0) {
				ccl.push_back(v);
				if (stt==v) stt=0;
			}
			return;
		}
	}
	tmpvis[v]=false;
}

void dfsvis(int v,vector<bool>& vis) {
	vis[v]=true;
	for (int i:cptG[v]) {
		if (vis[i]) continue;
		dfsvis(i,vis);
	}
}

void dfs2(int v,int p,vector<bool>& isccl) {
	if (cptG[v].size()==1) {
		dp[v][0]=0;
		dp[v][1]=-INF;
		return;
	}
	dp[v][0]=0;
	for (int i:cptG[v]) {
		if (i==p) continue;
		if (isccl[i]) continue;
		dfs2(i,v,isccl);
		dp[v][0]+=max(dp[i][0],dp[i][1]);
	}
	dp[v][1]=0;
	for (int i:cptG[v]) {
		if (i==p) continue;
		if (isccl[i]) continue;
		dp[v][1]=max(dp[v][1],dp[v][0]-max(dp[i][0],dp[i][1])+dp[i][0]+1);
	}
}
 
int main() {
	speed;
	cin>>n;
	vector<string> dct;
	for (int i=0;i<n;i++) {
		string a,b;
		cin>>a>>b;
		eg.emplace_back(a,b);
		dct.push_back(a);
		dct.push_back(b);
	}
	sort(all(dct));
	dct.resize(unique(all(dct))-dct.begin());
//	for (string s:dct) cout<<s<<"\n";
//	cout<<"name\n";
	fill(G,G+n,n);
	for (int i=0;i<n;i++) {
		auto [a,b]=eg[i];
		int va=lower_bound(all(dct),a)-dct.begin();
		int vb=lower_bound(all(dct),b)-dct.begin();
		G[va]=vb;
		if (va!=G[G[va]]) cptG[va].push_back(vb);
		if (va!=vb and va!=G[G[va]]) cptG[vb].push_back(va);
	}
//	for (int i=0;i<n;i++) {
//		cout<<i<<" : ";
//		for (int j:cptG[i]) cout<<j<<" ";
//		cout<<"\n";
//	}
	if (n&1) {
		cout<<"-1\n";
		return 0;
	}
	vector<bool> vis(n,0),tmpvis(n,0);
	vector<bool> isccl(n,0);
	int ttl=0;
	for (int i=0;i<n;i++) {
		if (vis[i]) continue;
		vector<int> ccl;
		int stt=-1;
		dfs(i,-1,vis,tmpvis,ccl,stt);
		dfsvis(i,vis);
//		cout<<i<<" i\n"<<flush;
//		for (int j:ccl) cout<<j<<" ";
//		cout<<" ccl\n"<<flush;
		for (int j:ccl) isccl[j]=true;
		for (int j:ccl) {
//			cout<<j<<" rt\n"<<flush;
			dfs2(j,-1,isccl);
		}
		vector<vector<int> > cdp(ccl.size(),vector<int>(2,0));
		cdp[0][0]=dp[ccl[0]][0];
		cdp[0][1]=dp[ccl[0]][1];
		for (i=1;i<ccl.size();i++) {
			cdp[i][0]=max(cdp[i-1][0],cdp[i-1][1])+dp[ccl[i]][0];
			cdp[i][1]=max(max(cdp[i-1][0],cdp[i-1][1])+dp[ccl[i]][1],cdp[i-1][0]+dp[ccl[i]][0]+1);
		}
		int ans=max(cdp[ccl.size()-1][0],cdp[ccl.size()-1][1]);
		int tmp=ccl[0];
		for (int j=0;j<ccl.size()-1;j++) ccl[j]=ccl[j+1];
		ccl[ccl.size()-1]=tmp;
		fill(all(cdp),vector<int>(2,0));
		cdp[0][0]=dp[ccl[0]][0];
		cdp[0][1]=dp[ccl[0]][1];
		for (i=1;i<ccl.size();i++) {
			cdp[i][0]=max(cdp[i-1][0],cdp[i-1][1])+dp[ccl[i]][0];
			cdp[i][1]=max(max(cdp[i-1][0],cdp[i-1][1])+dp[ccl[i]][1],cdp[i-1][0]+dp[ccl[i]][0]+1);
		}
		ans=max(ans,max(cdp[ccl.size()-1][0],cdp[ccl.size()-1][1]));
		ttl+=ans;
	}
	cout<<n-ttl<<"\n";
	return 0;
}

Compilation message (stderr)

polygon.cpp: In function 'int main()':
polygon.cpp:127:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   for (i=1;i<ccl.size();i++) {
      |            ~^~~~~~~~~~~
polygon.cpp:133:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for (int j=0;j<ccl.size()-1;j++) ccl[j]=ccl[j+1];
      |                ~^~~~~~~~~~~~~
polygon.cpp:138:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   for (i=1;i<ccl.size();i++) {
      |            ~^~~~~~~~~~~

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