oj.uz

Submission #530384

# Submission time Handle Problem Language Result Execution time Memory
530384 2022-02-25T09:19:03 Z fatemetmhr Love Polygon (BOI18_polygon) C++17
21 / 100
 212 ms 8464 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4296 KB Output is correct
2 Correct 60 ms 4312 KB Output is correct
3 Correct 48 ms 4352 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 46 ms 4352 KB Output is correct
8 Correct 48 ms 4304 KB Output is correct
9 Correct 49 ms 4396 KB Output is correct
10 Correct 58 ms 4324 KB Output is correct
11 Correct 48 ms 4312 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 169 ms 8464 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 8436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4296 KB Output is correct
2 Correct 60 ms 4312 KB Output is correct
3 Correct 48 ms 4352 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 46 ms 4352 KB Output is correct
8 Correct 48 ms 4304 KB Output is correct
9 Correct 49 ms 4396 KB Output is correct
10 Correct 58 ms 4324 KB Output is correct
11 Correct 48 ms 4312 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Incorrect 169 ms 8464 KB Output isn't correct
20 Halted 0 ms 0 KB -