oj.uz

Submission #415336

# Submission time Handle Problem Language Result Execution time Memory
415336 2021-05-31T22:12:10 Z Blagojce Love Polygon (BOI18_polygon) C++11
29 / 100
 185 ms 32804 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<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.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9676 KB Output is correct
2 Incorrect 7 ms 9676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 25460 KB Output is correct
2 Correct 168 ms 27532 KB Output is correct
3 Correct 117 ms 24756 KB Output is correct
4 Correct 142 ms 21416 KB Output is correct
5 Correct 150 ms 32804 KB Output is correct
6 Correct 151 ms 23936 KB Output is correct
7 Correct 184 ms 23984 KB Output is correct
8 Correct 136 ms 24036 KB Output is correct
9 Correct 137 ms 22996 KB Output is correct
10 Correct 81 ms 22012 KB Output is correct
11 Correct 7 ms 9676 KB Output is correct
12 Correct 8 ms 9676 KB Output is correct
13 Correct 6 ms 9736 KB Output is correct
14 Correct 6 ms 9732 KB Output is correct

Subtask #4
0 / 25.0

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