oj.uz

답안 #862865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862865 2023-10-19T07:09:24 Z maks007 Love Polygon (BOI18_polygon) C++14
0 / 100
 219 ms 8656 KB 
//Bismi Allah
#include "bits/stdc++.h"

using namespace std;

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	map <string,int> mp;
	vector <int> love(n, 0);
	/*vector <int> used(n, 0), dp(n, 0), g[n], unite(n, 0), loved(n, 0), rk(n, 0);
	function <void(int,int)> dfs=[&](int v, int p) {
		used[v] = 1;
		rk[v] = 1;
		for(auto u : g[v]) {
			if(used[u]) continue;
			dfs(u, v);
			rk[v] += rk[u];
		}
		if(unite[v]) return;
		if(p != -1 && unite[p] == 0) {
			unite[p] = 1;
			unite[v] = 1;
		}
	};*/
	for(int i = 0; i < n; i ++) {
		string u, v;
		cin >> u >> v;
		if(mp.count(u) == 0) mp[u] = mp.size();
		if(mp.count(v) == 0) mp[v] = mp.size();
		love[mp[u]] = mp[v];
	}
	if(n <= 20) {
		vector <int> forMask;
		for(int mask = 0; mask < (1 << n); mask ++) {
			if(__builtin_popcount(mask) % 2 != 0) continue;
			forMask.push_back(mask);
		}
		sort(forMask.begin(), forMask.end(), [](int a, int b) {
			return __builtin_popcount(a) < __builtin_popcount(b);
		});
		vector <int> dp(1 << n, 1e9);
		dp[0] = 0;
		for(auto mask : forMask) {
			if(mask == 0) continue;
			vector <int> v;
			for(int i = 0; i < n; i ++) {
				if(mask & (1 << i)) {
					v.push_back(i);
				}
			}
			for(int i = 0; i < v.size(); i ++) {
				for(int j = i + 1; j < v.size(); j ++) {
					int cost = 0, newmask = mask;
					newmask ^= (1 << v[i]);
					newmask ^= (1 << v[j]);
					if(love[v[i]] == v[j] && love[v[j]] == v[i]) cost = 0;
					else if(love[v[i]] == v[j] || love[v[j]] == v[i]) cost = 1;
					else cost = 2;
					dp[mask] = min(dp[mask], dp[newmask] + cost);
				}
			}
		}
		cout << dp[(1 << n) - 1];
		return 0;
	}
	/*if(*min_element(loved.begin(), loved.end()) >= 1) {
		if(n % 2 == 1) {
		//	assert(false);
			cout << -1;
			return 0;
		}
		int ans = 0, mod = 0;
		for(int i = 0; i < n; i ++) {
			if(used[i]) continue;
			dfs(i, -1);
			if(rk[i] == 2) continue;
			ans += rk[i] / 2;
			mod += (rk[i] % 2);
		}
		if(mod % 2 == 1) cout << -1;
		else cout << ans + mod;
		return 0;
	}
	if(n % 2 == 1) {
	//	assert(false);
		cout << -1;
		return 0;
	}
	int ans = 0, mod = 0;
	for(int i = 0; i < n; i ++) {
		if(used[i]) continue;
		dfs(i, -1);
	}
	for(auto i : unite) {
		ans += (i == 1);
		mod += (i == 0);
	}
	cout << ans/2+mod;*/
	
	return 0;
}

Compilation message

polygon.cpp: In function 'int main()':
polygon.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for(int i = 0; i < v.size(); i ++) {
      |                   ~~^~~~~~~~~~
polygon.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j = i + 1; j < v.size(); j ++) {
      |                        ~~^~~~~~~~~~

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 6600 KB Output is correct
2 Correct 193 ms 6740 KB Output is correct
3 Correct 219 ms 6736 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 135 ms 8656 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 136 ms 8652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 6600 KB Output is correct
2 Correct 193 ms 6740 KB Output is correct
3 Correct 219 ms 6736 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -