oj.uz

Submission #415341

# Submission time Handle Problem Language Result Execution time Memory
415341 2021-05-31T22:56:32 Z Blagojce Love Polygon (BOI18_polygon) C++11
54 / 100
 182 ms 30640 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9740 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Incorrect 7 ms 9724 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 7 ms 9616 KB Output is correct
3 Correct 7 ms 9724 KB Output is correct
4 Correct 168 ms 25968 KB Output is correct
5 Correct 182 ms 26040 KB Output is correct
6 Correct 146 ms 26100 KB Output is correct
7 Correct 125 ms 22936 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 23348 KB Output is correct
2 Correct 167 ms 25268 KB Output is correct
3 Correct 108 ms 27568 KB Output is correct
4 Correct 120 ms 19488 KB Output is correct
5 Correct 167 ms 30640 KB Output is correct
6 Correct 124 ms 21800 KB Output is correct
7 Correct 168 ms 21812 KB Output is correct
8 Correct 134 ms 24600 KB Output is correct
9 Correct 118 ms 20856 KB Output is correct
10 Correct 80 ms 19848 KB Output is correct
11 Correct 7 ms 9676 KB Output is correct
12 Correct 7 ms 9680 KB Output is correct
13 Correct 9 ms 9672 KB Output is correct
14 Correct 6 ms 9676 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9740 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Incorrect 7 ms 9724 KB Output isn't correct
9 Halted 0 ms 0 KB -