Submission #415341

#	Time	Username	Problem	Language	Result	Execution time	Memory
415341		Blagojce	Love Polygon (BOI18_polygon)	C++11	54 / 100	182 ms	30640 KiB

polygon

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;

mt19937 _rand(time(NULL));
const int mxn = 2e5;

bool vis[mxn];

int n;
vector<int> g[mxn];
vector<int> tree[mxn];


int link[mxn];

unordered_map<string, int> mapa;


vector<vector<int> > R;

vector<int> r;

void mark(int u){
	vis[u] = true;
	for(auto e : g[u]){
		if(vis[e]) continue;
		tree[u].pb(e);
		mark(e);
	}
}

void find_roots(){
	fr(i, 0, n){
		if(vis[i]) continue;
		int x = i;
		
		vector<int> undo;
		
		while(!vis[x]){
			vis[x] = true;
			undo.pb(x);
			x = link[x];
		}
		int a = x;
		vector<int> v;
		
		do{
			v.pb(a);
			a = link[a];
		}while(a != x);
		
		R.pb(v);
		
		for(auto u : undo) vis[u] = false;
		for(auto u : v) vis[u] = true;
		
		for(auto u : v){
			r.pb(u);
			mark(u);
		}
	}
}
int dp[mxn][2];

void dfs(int u){
	for(auto e : tree[u]){
		dfs(e);
	}
	
	int minsum = 0;
	for(auto e : tree[u]){
		minsum += min(dp[e][0], dp[e][1]);
	}
	dp[u][0] = dp[u][1] = minsum + 1;
	for(auto e : tree[u]){
		int tempsum = minsum - min(dp[e][0], dp[e][1]) + dp[e][0];
		dp[u][1] = min(dp[u][1], tempsum);
	}
}
bool used[mxn];
int ans;

void solve(){
	cin >> n;
	
	int c = 0;
	
	fr(i, 0, n){
		link[i] = i;
	}
	
	fr(i, 0, n){
		string s;
		cin >> s;
		if(mapa[s] == 0){
			mapa[s] = ++c;
		}
		int u = mapa[s]-1;
		cin >> s;
		if(mapa[s] == 0){
			mapa[s] = ++c;
		}
		int v = mapa[s]-1;
		link[u] = v;
		
		g[v].pb(u);
	}
	
	
	
	if(n % 2){
		cout<<-1<<endl;
		return;
	}
	
	find_roots();
	
	for(auto u : r){
		dfs(u);	
	}
	
	for(auto vec : R){
		int len = (int)vec.size();
		fr(i, 0, len){
			int u = vec[i];
			used[i] = dp[u][1] >= dp[u][0];
			ans += min(dp[u][1], dp[u][0]);
		}
		int l = 0;
		fr(i, 0, len){
			if(used[i]) ++l;
			else break;
		}
		
		
		
		if(l == len){
			if(l == 2){
				ans -= 2;
			}
			else ans -= len/2;
		}
		else{
			int r = 0;
			for(int i = len - 1; i >= 0; i --){
				if(used[i]) ++r;
				else break;
			}
			int con = 0;
			vector<int> tr;
			tr.pb(l+r);
			fr(i, l, len-r){
				if(used[i]) con ++;
				else{
					if(con > 0) tr.pb(con);
					con = 0;
				}
			}
			if(con > 0){
				tr.pb(con);
			}
			for(auto u : tr){
				
				ans -= u/2;
			}
		}	
		
	}
	cout<<ans<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	
}

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