Submission #530379

#	Time	Username	Problem	Language	Result	Execution time	Memory
530379		fatemetmhr	Love Polygon (BOI18_polygon)	C++17	54 / 100	251 ms	27796 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 pd[maxn5], num[maxn5];
int sz[maxn5], parof[maxn5];
map <string, int> av;
bool mark[maxn5], incy[maxn5];
vector <int> adj[maxn5], ver, tmp;
int nn = 0, cmp[maxn5];

inline int dfs2(int v){
	//cout << "hello " << v << endl;
	mark[v] = true;
	int cy = -1;
	int u = parof[v];
	cmp[v] = nn;
	//cout << "ok " << v << ' ' << u << endl;
	if(!mark[u]){
		int z = dfs2(u);
		//cout << "aha " << z << endl;
		if(cy == -1)
			cy = z;
	}
	else if(cmp[u] == cmp[v]){
		cy = u;
	}
	//cout << ' ' << v << ' ' << cy << endl;
	if(cy != -1)
		incy[v] = true;
	return (cy == v ? -1 : cy);
}

inline void dfs(int v){
	//cout << "hello " << v << endl;
	dp[0][v] = 0;
	sz[v] = 1;
	bool re = false;
	for(auto u : adj[v]) if(!incy[u]){
		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]) if(!incy[u]){
		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;
}

inline int find_next(int v){
	return parof[v];
}

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++;
		adj[av[t]].pb(av[s]);
		parof[av[s]] = av[t];
	}
	/*
	for(auto it = av.begin(); it != av.end(); it++)
		cout << (it -> fi) << ' ' << (it -> se) << endl;
	//*/
	if(n % 2 == 1)
		return cout << -1 << endl, 0;
	memset(mark, false, sizeof mark);
	for(int i = 0; i < n; i++) if(!mark[i]){
		dfs2(i);
		nn++;
	}
	for(int i = 0; i < n; i++) if(incy[i]){
		dfs(i);
	}
	memset(mark, false, sizeof mark);
	ll ans = 0;
	for(int i = 0; i < n; i++) if(incy[i] && !mark[i]){
		//cout << "oh a new day! " << i << endl;
		ver.clear();
		int v = find_next(i);
		mark[i] = true;
		ver.pb(i);
		while(v != i){
			mark[v] = true;
			ver.pb(v);
			v = find_next(v);
			//cout << v << ' ' << i << endl;
		}
		if(ver.size() == 1){
			ans += dp[1][i];
			if(sz[i] % 2 == 1)
				ans++;
			continue;
		}
		pd[0] = dp[1][i];
		num[0] = sz[i];
		for(int j = 1; j < ver.size(); j++){
			int u = ver[j];
			num[j] = num[j - 1] + sz[u];
			pd[j] = pd[j - 1] + dp[1][u] + 2 * (num[j - 1] % 2 == 1 && sz[u] % 2 == 1);
			int val = (j == 1 ? 0 : pd[j - 2]) + dp[0][u] + dp[0][ver[j - 1]] + 1;
			int f = (sz[u] % 2 == 0) + (sz[ver[j - 1]] % 2 == 0) + (j > 1 && num[j - 2] % 2 == 1);
			if(f >= 2)
				val += 2;
			pd[j] = min(pd[j], val);
			val = pd[j - 1] + dp[0][u] + 2 * (num[j - 1] % 2 == 1 && sz[u] % 2 == 0);
			if(num[j] % 2 == 1)
				pd[j] = min(pd[j], val);
		}
		int cur = pd[ver.size() - 1] + (num[ver.size() - 1] % 2);
		tmp.clear();
		tmp.pb(ver.back());
		for(auto u : ver)
			tmp.pb(u);
		tmp.pop_back();
		ver.clear();
		for(auto u : tmp)
			ver.pb(u);
		pd[0] = dp[1][i];
		num[0] = sz[i];
		for(int j = 1; j < ver.size(); j++){
			int u = ver[j];
			num[j] = num[j - 1] + sz[u];
			pd[j] = pd[j - 1] + dp[1][u] + 2 * (num[j - 1] % 2 == 1 && sz[u] % 2 == 1);
			int val = (j == 1 ? 0 : pd[j - 2]) + dp[0][u] + dp[0][ver[j - 1]] + 1;
			int f = (sz[u] % 2 == 0) + (sz[ver[j - 1]] % 2 == 0) + (j > 1 && num[j - 2] % 2 == 1);
			if(f >= 2)
				val += 2;
			pd[j] = min(pd[j], val);
			val = pd[j - 1] + dp[0][u] + 2 * (num[j - 1] % 2 == 1 && sz[u] % 2 == 0);
			if(num[j] % 2 == 1)
				pd[j] = min(pd[j], val);
		}
		cur = min(cur, pd[ver.size() - 1] + (num[ver.size() - 1] % 2));
		if(ver.size() == 2){
			cur = min(cur, dp[0][ver[0]] + dp[0][ver[1]] + 2 * (sz[ver[0]] % 2 == 0 && sz[ver[1]] % 2 == 0));
		}
		ans += cur;
	}

	cout << ans << endl;
}

Compilation message (stderr)

polygon.cpp: In function 'int main()':
polygon.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   for(int j = 1; j < ver.size(); j++){
      |                  ~~^~~~~~~~~~~~
polygon.cpp:158:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |   for(int j = 1; j < ver.size(); j++){
      |                  ~~^~~~~~~~~~~~

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