제출 #530363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530363		fatemetmhr	Love Polygon (BOI18_polygon)	C++17	29 / 100	230 ms	28920 KiB

polygon

#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
• Subtask 2: 0 / 25
• Subtask 3: 29 / 29
• Subtask 4: 0 / 25