제출 #530384

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530384		fatemetmhr	Love Polygon (BOI18_polygon)	C++17	21 / 100	212 ms	8464 KiB

polygon

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;


#define pb    push_back
#define fi    first
#define se    second

const int maxn5 = 2e6 + 10;

int parof[maxn5];

int dp[maxn5];
map <string, int> av;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int n; cin >> n;
	int ind = 0;
	for(int i = 0; i < n; i++){
		string s, t; cin >> s >> t;
		if(av.find(s) == av.end())
			av[s] = ind++;
		if(av.find(t) == av.end())
			av[t] = ind++;
		parof[av[s]] = av[t];
	}
	/*
	for(auto it = av.begin(); it != av.end(); it++)
		cout << (it -> fi) << ' ' << (it -> se) << endl;
	//*/
	if(n % 2 == 1)
		return cout << -1 << endl, 0;
	for(int mask = 1; mask < (1 << n); mask++) if(__builtin_popcount(mask) % 2 == 0){
		int v = 0;
		for(int i = 0; i < n; i++) if((mask >> i)&1)
			v = i;
		dp[mask] = n + 2;
		for(int i = 0; i < v; i++) if((mask >> i)&1)
			dp[mask] = min(dp[mask], dp[mask ^ (1 << v) ^ (1 << i)] + (parof[i] != v) + (parof[v] != i));
	} 
	cout << dp[(1 << n) - 1] << endl;
}

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