Submission #415336

#	Time	Username	Problem	Language	Result	Execution time	Memory
415336		Blagojce	Love Polygon (BOI18_polygon)	C++11	29 / 100	185 ms	32804 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<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);
		
		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);
	}
}


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();
	
	int ans = 0;
	for(auto u : r){
		dfs(u);
		
		ans += min(dp[u][0], dp[u][1]);
	}
	cout<<ans<<endl;
}

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

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