Submission #1108169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108169		_rain_	Love Polygon (BOI18_polygon)	C++14	21 / 100	291 ms	20712 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];
	}
}

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

	cin>>n;
	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 (sub1::check()){
		sub1::main_code();
		exit(0);
	}
	exit(0);
}

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