Submission #949144

#	Time	Username	Problem	Language	Result	Execution time	Memory
949144		koukirocks	Love Polygon (BOI18_polygon)	C++17	46 / 100	133 ms	21508 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];

void dfs(int v,int p,vector<int>& sz) {
	sz[v]=1;
	for (int i:cptG[v]) {
		if (i==p) continue;
		dfs(i,v,sz);
		sz[v]+=sz[i];
	}
}

int dfs2(int v,int p,bool can,vector<int>& sz) {
//	cout<<v<<" "<<p<<" "<<can<<"\n";
	if (sz[v]==1) return can;
	int ans=0;
	int minn=INF;
	int id=0;
	if (can) {
		for (int i:cptG[v]) {
			if (i==p) continue;
			if (sz[i]<minn) {
				minn=sz[i];
				id=i;
			}
		}
		ans+=dfs2(id,v,0,sz)+1;
	}
	for (int i:cptG[v]) {
		if (i==p) continue;
		if (can and i==id) continue;
		ans+=dfs2(i,v,1,sz);
	}
	return ans;
}

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());
	vector<int> lvd(n,0);
	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;
		cptG[va].push_back(vb);
		cptG[vb].push_back(va);
		lvd[vb]++;
	}
	bool alllvd=true;
	for (int i=0;i<n;i++) {
		if (lvd[i]!=1) {
			alllvd=false;
			break;
		}
	}
	if (n&1) {
		cout<<"-1\n";
		return 0;
	}
	if (n<=20) {
		int ans=n;
		for (int st=0;st<(1<<n);st++) {
			bool flag=true;
			vector<int> cnt(n,0);
			for (int i=0;i<n;i++) {
				if (st&(1<<i)) continue;
				if (G[i]==i) {
					flag=false;
					break;
				}
				int tgt=G[i];
				if (G[tgt]==i) continue;
				if (st&(1<<tgt)) {
					if (cnt[tgt]==0) {
						cnt[tgt]++;
						continue;
					}
				}
				flag=false;
				break;
			}
	//		if (flag) cout<<st<<"\n";
			if (flag) ans=min(ans,__builtin_popcount(st));
		}
		cout<<ans<<"\n";
	} else if (alllvd) {
		vector<bool> vis(n,0);
		int ans=0;
		for (int i=0;i<n;i++) {
			if (vis[i]) continue;
			int now=i;
			int st=i;
			int sz=1;
			vis[i]=true;
			while (G[now]!=st) {
//				cout<<now<<" ";
				sz++;
				now=G[now];
				vis[now]=true;
			}
			if (sz==2) continue;
			ans+=(sz+1)>>1;
		}
		cout<<ans<<"\n";
	} else {
		vector<int> sz(n);
		int ans=0;
		for (int i=0;i<n;i++) {
			if (G[i]==i) {
				dfs(i,i,sz);
				ans+=dfs2(i,i,1,sz);
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

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