Submission #977252

#	Time	Username	Problem	Language	Result	Execution time	Memory
977252		Isam	Love Polygon (BOI18_polygon)	C++17	21 / 100	1612 ms	33228 KiB

polygon

#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];
}

unordered_set<int> obino;

inline int solv(){
	
	
	
	shuffle(all(st), rng);
	
	int ans(0);
	
	obino.clear();
	
	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;
	
	obino.clear();
	
	
	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 = 50;
	
	while(cnt--) ans = min(ans, solv());
	
	
	
	
	
	
	cout << ans << '\n';
	
	return 0;
}

/*
1 2 +1


2 6
6 3
3 2








4 5



*/

Compilation message (stderr)

polygon.cpp: In function 'int solv()':
polygon.cpp:41:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   41 |  for(register int i = 1; i <= n; ++i){
      |                   ^
polygon.cpp:47:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   47 |  register int j(0);
      |               ^
polygon.cpp: In function 'int main()':
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) st.eb(i);
      |                   ^
polygon.cpp:106:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  106 |  for(register int i = 1; i <= n; ++i){
      |                   ^
polygon.cpp:136:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  136 |  register int j(0);
      |               ^

• Subtask 1: 21 / 21
• Subtask 2: 0 / 25
• Subtask 3: 0 / 29
• Subtask 4: 0 / 25