oj.uz

Submission #862879

# Submission time Handle Problem Language Result Execution time Memory
862879 2023-10-19T07:46:23 Z iskhakkutbilim Love Polygon (BOI18_polygon) C++17
46 / 100
 543 ms 39620 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];
vector<int> G[N+10];
int idx[N+10];
vector<int> topo;
int num=1;

vector<int> sub[N+10];

void dfs(int v){
	used[v] = 1;
	for(int to : g[v]){
		if(!used[to]){
			dfs(to);
		}
	}
	topo.push_back(v);
}

void dfs2(int v){
	used[v] = 1;
	idx[v] = num;
	sub[num].push_back(v);
	for(int to : G[v]){
		if(!used[to]){
			dfs2(to);
		}
	}
}

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]]);
		G[compress[b[i]]].push_back(compress[a[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]){
			dfs(i);
		}
	}
	reverse(all(topo));
	for(int i = 1;i <= n; i++) used[i] = 0;
	for(int i : topo){
		if(!used[i]){
			dfs2(i);
			num++;
		}
	}
	for(int i = 1;i <= n; i++){
		int cnt = sub[i].size();
		if(cnt > 2){
			ans+= (cnt / 2);
			
		}
		self+= (cnt%2);
	}
	ans+= self;
	
	
	
	cout << ans;
	return 0;
}

Compilation message

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

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 17252 KB Output is correct
2 Correct 543 ms 17244 KB Output is correct
3 Correct 522 ms 17244 KB Output is correct
4 Correct 2 ms 9048 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 522 ms 17244 KB Output is correct
8 Correct 528 ms 17240 KB Output is correct
9 Correct 522 ms 17240 KB Output is correct
10 Correct 526 ms 17240 KB Output is correct
11 Correct 521 ms 17244 KB Output is correct
12 Correct 2 ms 9048 KB Output is correct
13 Correct 2 ms 9052 KB Output is correct
14 Correct 2 ms 9052 KB Output is correct
15 Correct 2 ms 9304 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 203 ms 39448 KB Output is correct
5 Correct 207 ms 34500 KB Output is correct
6 Correct 201 ms 39620 KB Output is correct
7 Correct 221 ms 32776 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 17252 KB Output is correct
2 Correct 543 ms 17244 KB Output is correct
3 Correct 522 ms 17244 KB Output is correct
4 Correct 2 ms 9048 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 522 ms 17244 KB Output is correct
8 Correct 528 ms 17240 KB Output is correct
9 Correct 522 ms 17240 KB Output is correct
10 Correct 526 ms 17240 KB Output is correct
11 Correct 521 ms 17244 KB Output is correct
12 Correct 2 ms 9048 KB Output is correct
13 Correct 2 ms 9052 KB Output is correct
14 Correct 2 ms 9052 KB Output is correct
15 Correct 2 ms 9304 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 2 ms 9052 KB Output is correct
19 Correct 203 ms 39448 KB Output is correct
20 Correct 207 ms 34500 KB Output is correct
21 Correct 201 ms 39620 KB Output is correct
22 Correct 221 ms 32776 KB Output is correct
23 Incorrect 233 ms 36032 KB Output isn't correct
24 Halted 0 ms 0 KB -