oj.uz

Submission #862876

# Submission time Handle Problem Language Result Execution time Memory
862876 2023-10-19T07:44:07 Z iskhakkutbilim Love Polygon (BOI18_polygon) C++17
46 / 100
 539 ms 29272 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1e5;
 
int n;
vector<string> a, b;
vector<string> compr;
map<string,int> compress;
vector<int> g[N+10];
int used[N + 10];
 
int cnt, loves;
void dfs(int v){
	used[v] = 1;
	cnt++;
	for(int to : g[v]){
		if(used[to] == 0){
			dfs(to);
		}else if(used[to] == 1){
			loves++;
		}
	}
	used[v] = 2;
}
 
 
main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n;
	a.resize(n);
	b.resize(n);
	for(int i = 0;i < n; i++){
		cin >> a[i] >> b[i];
		compr.push_back(a[i]);
	}
	sort(all(compr));
	int cnt1 = 1;
	for(auto x : compr){
		compress[x] = cnt1++;
	}
	for(int i = 0;i < n; i++){
		g[compress[a[i]]].push_back(compress[b[i]]);
	}
	if(n%2 == 1){
		cout << "-1";
		return 0;
	}
	if(n <= 20){
		vector<int> dp((1<<n), INT_MAX);
		dp[0] = 0;
		for(int mask = 0; mask < (1<<n); mask++){
			for(int i = 0;i < n; i++){
				for(int j = i + 1; j < n; j++){
					int new_mask = mask | (1<<i);
					new_mask|= (1<<j);
					int c = (g[i+1][0] != j + 1) + (g[j + 1][0] != (i + 1));
					dp[new_mask] = min(dp[new_mask], dp[mask] + c);
				}
			}
		}
		cout << dp[(1<<n)-1];
		return 0;
	}
	int ans = 0, self = 0;
	for(int i = 1;i <= n; i++){
		if(!used[i]){
			cnt = 0;
			dfs(i);
			if(cnt > 2) ans = ans + (cnt / 2);
			self = self + (cnt % 2);
		}
	}
	ans+= self;
	cout << ans;
	return 0;
}

Compilation message

polygon.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      | ^~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 11608 KB Output is correct
2 Correct 517 ms 11612 KB Output is correct
3 Correct 518 ms 11608 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 539 ms 11612 KB Output is correct
8 Correct 531 ms 11608 KB Output is correct
9 Correct 519 ms 11612 KB Output is correct
10 Correct 521 ms 11612 KB Output is correct
11 Correct 533 ms 11608 KB Output is correct
12 Correct 1 ms 3420 KB Output is correct
13 Correct 1 ms 3420 KB Output is correct
14 Correct 1 ms 3420 KB Output is correct
15 Correct 1 ms 3420 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 178 ms 28132 KB Output is correct
5 Correct 159 ms 24132 KB Output is correct
6 Correct 160 ms 29272 KB Output is correct
7 Correct 157 ms 24544 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 11608 KB Output is correct
2 Correct 517 ms 11612 KB Output is correct
3 Correct 518 ms 11608 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 539 ms 11612 KB Output is correct
8 Correct 531 ms 11608 KB Output is correct
9 Correct 519 ms 11612 KB Output is correct
10 Correct 521 ms 11612 KB Output is correct
11 Correct 533 ms 11608 KB Output is correct
12 Correct 1 ms 3420 KB Output is correct
13 Correct 1 ms 3420 KB Output is correct
14 Correct 1 ms 3420 KB Output is correct
15 Correct 1 ms 3420 KB Output is correct
16 Correct 1 ms 3420 KB Output is correct
17 Correct 1 ms 3420 KB Output is correct
18 Correct 1 ms 3420 KB Output is correct
19 Correct 178 ms 28132 KB Output is correct
20 Correct 159 ms 24132 KB Output is correct
21 Correct 160 ms 29272 KB Output is correct
22 Correct 157 ms 24544 KB Output is correct
23 Incorrect 150 ms 23732 KB Output isn't correct
24 Halted 0 ms 0 KB -