Submission #1108242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108242		_rain_	Love Polygon (BOI18_polygon)	C++14	46 / 100	311 ms	18948 KiB

polygon

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define name "main"

const int N=(int)1e5;
int deg[N+2],to[N+2],u[N+2],v[N+2],n;
string s1[N+2],s2[N+2];
vector<string>nen;

namespace sub1{
	bool check(){
		return n<=20;
	}
	#define BIT(mask,x) (((mask)>>(x))&(1))
	#define MASK(x) ((1)<<(x))
	const int NN=20;
	int dp[MASK(NN)];
	void main_code(){
		memset(dp,0x3f,sizeof dp);
		dp[0]=0;
		int INF=dp[1];
		for(int mask=0;mask<MASK(n);++mask){
			for(int i=1;i<=n;++i){
				if (BIT(mask,i-1)) continue;
				for(int k=i+1;k<=n;++k){
					if (!BIT(mask,k-1)){
						dp[mask|MASK(i-1)|MASK(k-1)]=min(dp[mask|MASK(i-1)|MASK(k-1)],dp[mask]+(to[i]!=k)+(to[k]!=i));
					}
				}
			}
		}
		if (dp[MASK(n)-1]==INF) dp[MASK(n)-1]=-1;
		cout<<dp[MASK(n)-1];
	}
}

namespace sub2{
	bool check(){
		for(int i=1;i<=n;++i){
			if (deg[i]==0) return false;
		}
		return true;
	}
	const int NN=(int)3e5;
	bool used[NN+2];
	void main_code(){
		int ans=0;
		for(int i=1;i<=n;++i){
			int cnt=0;
			for(int j=i;!used[j];j=to[j]) {
				used[j]=true;
				++cnt;
			}
			if (cnt!=2) ans+=(cnt+1)/2;
		}
		cout<<ans<<'\n';
	}
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// freopen(name".inp","r",stdin);
	// freopen(name".out","w",stdout);
	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];
		deg[v[i]]++;
	}
	// for(int i=1;i<=n;++i) if (deg[i]==0)
	if (sub1::check()){
		sub1::main_code();
		exit(0);
	}
	if (sub2::check()){
		sub2::main_code();
		exit(0);
	}
	exit(0);
}

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