oj.uz

Submission #530363

# Submission time Handle Problem Language Result Execution time Memory
530363 2022-02-25T08:12:09 Z fatemetmhr Love Polygon (BOI18_polygon) C++17
29 / 100
 230 ms 28920 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;


#define pb    push_back
#define fi    first
#define se    second

const int maxn5 = 3e5 + 10;

int a[maxn5], req[maxn5];

int dp[2][maxn5]; // dp[0 -> khodesh nabashad/ 1 -> bashad][v]
int sz[maxn5];
map <string, int> av;
bool mark[maxn5];
vector <int> adj[maxn5];

inline void dfs(int v){
	//cout << "hello " << v << endl;
	dp[0][v] = 0;
	sz[v] = 1;
	bool re = false;
	for(auto u : adj[v]){
		dfs(u);
		sz[v] += sz[u];
		dp[0][v] += dp[1][u] + (sz[u] % 2);
		re = true;
	}
	if(!re){
		dp[1][v] = 0;
		return;
	}
	dp[1][v] = maxn5;
	for(auto u : adj[v]){
		int val = dp[0][v] - dp[1][u] - (sz[u] % 2);
		val += dp[0][u] + (sz[u] % 2 == 0);
		val++;
		if(sz[v] % 2 == 1)
			val--;
		dp[1][v] = min(dp[1][v], val);
	}
	if(sz[v] % 2 == 0){
		dp[0][v]--;
	}
	else{
		dp[1][v] = min(dp[1][v], dp[0][v]);
	}
	//cout << v << ' ' << dp[0][v] << ' ' << dp[1][v] << endl;
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int n; cin >> n;
	int ind = 0;
	for(int i = 0; i < n; i++){
		string s, t; cin >> s >> t;
		if(av.find(s) == av.end())
			av[s] = ind++;
		if(av.find(t) == av.end())
			av[t] = ind++;
		if(t != s){
			adj[av[t]].pb(av[s]);
			mark[av[s]] = true;
		}
	}
	/*
	for(auto it = av.begin(); it != av.end(); it++)
		cout << (it -> fi) << ' ' << (it -> se) << endl;
	*/
	if(n % 2 == 1)
		return cout << -1 << endl, 0;
	ll ans = 0;
	for(int i = 0; i < n; i++) if(!mark[i]){
		dfs(i);
		ans += dp[1][i];
		if(sz[i] % 2 == 1)
			ans++;
	}
	cout << ans << endl;
}

Subtask #1
0 / 21.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7368 KB Output is correct
3 Incorrect 4 ms 7372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 20972 KB Output is correct
2 Correct 224 ms 22880 KB Output is correct
3 Correct 108 ms 18520 KB Output is correct
4 Correct 201 ms 19016 KB Output is correct
5 Correct 228 ms 28920 KB Output is correct
6 Correct 230 ms 20196 KB Output is correct
7 Correct 211 ms 20164 KB Output is correct
8 Correct 162 ms 19712 KB Output is correct
9 Correct 204 ms 19660 KB Output is correct
10 Correct 146 ms 19000 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 4 ms 7372 KB Output is correct
13 Correct 4 ms 7372 KB Output is correct
14 Correct 4 ms 7372 KB Output is correct

Subtask #4
0 / 25.0

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