Submission #949124

#	Time	Username	Problem	Language	Result	Execution time	Memory
949124		koukirocks	Love Polygon (BOI18_polygon)	C++17	21 / 100	106 ms	18300 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];

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 (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 (n&1) {
		cout<<"-1\n";
		return 0;
	}
	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";
	return 0;
}

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