oj.uz

Submission #977243

# Submission time Handle Problem Language Result Execution time Memory
977243 2024-05-07T14:52:40 Z Isam Love Polygon (BOI18_polygon) C++17
21 / 100
 2000 ms 33420 KB 
#include<bits/stdc++.h>
using namespace std;

#define eb emplace_back
#define all(x) begin(x),end(x)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

constexpr int sz = 1e5 + 5;

int n, tot, degree[sz];

string s1, s2;

unordered_map<string, int> mp;

unordered_map<int, bool> g[sz];

int k, ansl;

vector<int> st;

bool vis[sz], mekni[sz], mki[sz];

bool cmp(int c, int d){
	return degree[c] < degree[d];
}

int solv(){
	
	
	
	shuffle(all(st), rng);
	
	int ans(0);
	
	set<int> obino;
	
	for(register int i = 1; i <= n; ++i){
		mekni[i] = mki[i];
		vis[i] = mki[i];
	}
	
	
	register int j(0);
	
	while(j < (int)st.size()){
		
		if(mekni[st[j]]){
			++j;
			continue;
		}
		
		int u = st[j], v = -1;
		
		for(auto &to : g[u]){
			if(vis[to.first] || to.second == false) continue;
			
			v = to.first;
			
			break;
			
			
		}
		
		if(v == -1){
			obino.insert(u);
			mekni[u] = 1;
			continue;
		}
		
		vis[v] = 1;
		
		mekni[v] = 1;
		
		vis[u] = 1;
		
		++ans;
		
		
	}
	
	int t(0);
	
	for(auto &to : obino){
		if(vis[to]) continue;
		++t;
	}
	
	ans += t;
	
	
	return ans;
}


signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	
	
	for(register int i = 1; i <= n; ++i) st.eb(i);
	
	for(register int i = 1; i <= n; ++i){
		cin >> s1 >> s2;
		if(mp[s1] == 0) mp[s1] = ++tot;
		if(mp[s2] == 0) mp[s2] = ++tot;
		
		int u = mp[s1], v = mp[s2];
		
		if(u == v) continue;
		
		degree[u]++, degree[v]++;
		
		g[u][v] = 1;
		
		if(g[v][u] == 1) ++k, mki[v] = mki[u] = mekni[v] = mekni[u] = vis[v] = vis[u] = 1; 
		
	}
	
	int ans(0);
	
	sort(all(st), cmp);
	
	mp.clear();
	
	if(n & 1) return cout << -1 << '\n', 0;
	
	if(k == n/2) return cout << 0 << '\n', 0;
	
	set<int> obino;
	
	
	register int j(0);
	
	while(j < (int)st.size()){
		
		if(mekni[st[j]]){
			++j;
			continue;
		}
		
		int u = st[j], v = -1;
		
		for(auto &to : g[u]){
			if(vis[to.first] || to.second == false) continue;
			
			v = to.first;
			
			break;
			
			
		}
		
		if(v == -1){
			obino.insert(u);
			mekni[u] = 1;
			continue;
		}
		
		vis[v] = 1;
		
		mekni[v] = 1;
		
		vis[u] = 1;
		
		++ans;
		
		
	}
	
	int t(0);
	
	for(auto &to : obino){
		if(vis[to]) continue;
		++t;
	}
	
	ans += t;
	
	int cnt = 100;
	
	while(cnt--) ans = min(ans, solv());
	
	
	
	
	
	
	cout << ans << '\n';
	
	return 0;
}

/*
1 2 +1


2 6
6 3
3 2








4 5



*/

Compilation message

polygon.cpp: In function 'int solv()':
polygon.cpp:39:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   39 |  for(register int i = 1; i <= n; ++i){
      |                   ^
polygon.cpp:45:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   45 |  register int j(0);
      |               ^
polygon.cpp: In function 'int main()':
polygon.cpp:102:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  102 |  for(register int i = 1; i <= n; ++i) st.eb(i);
      |                   ^
polygon.cpp:104:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  104 |  for(register int i = 1; i <= n; ++i){
      |                   ^
polygon.cpp:134:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  134 |  register int j(0);
      |               ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 3 ms 5980 KB Output is correct
5 Correct 2 ms 6076 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5976 KB Output is correct
8 Correct 3 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 6076 KB Output is correct
11 Correct 2 ms 6084 KB Output is correct
12 Correct 2 ms 5980 KB Output is correct
13 Correct 2 ms 5980 KB Output is correct
14 Correct 2 ms 5980 KB Output is correct
15 Correct 2 ms 5980 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 6076 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Execution timed out 2044 ms 33420 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 32908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 3 ms 5980 KB Output is correct
5 Correct 2 ms 6076 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5976 KB Output is correct
8 Correct 3 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 6076 KB Output is correct
11 Correct 2 ms 6084 KB Output is correct
12 Correct 2 ms 5980 KB Output is correct
13 Correct 2 ms 5980 KB Output is correct
14 Correct 2 ms 5980 KB Output is correct
15 Correct 2 ms 5980 KB Output is correct
16 Correct 2 ms 5980 KB Output is correct
17 Correct 2 ms 6076 KB Output is correct
18 Correct 2 ms 5980 KB Output is correct
19 Execution timed out 2044 ms 33420 KB Time limit exceeded
20 Halted 0 ms 0 KB -