Submission #949129

#	Time	Username	Problem	Language	Result	Execution time	Memory
949129		koukirocks	Love Polygon (BOI18_polygon)	C++17	0 / 100	2092 ms	14616 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;
	}
//	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 {
		int ans=0;
		for (int i=0;i<n;i++) {
			int now=i;
			int st=i;
			int sz=1;
			while (G[now]!=st) {
				sz++;
				now=G[now];
			}
			ans+=(sz+1)>>1;
		}
		cout<<ans<<"\n";
//	}
	return 0;
}

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