Submission #667176

#	Time	Username	Problem	Language	Result	Execution time	Memory
667176		Kahou	Love Polygon (BOI18_polygon)	C++14	100 / 100	116 ms	22936 KiB

polygon

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5 + 50;
int n, dp[N][2], dp2[N][2], vis[N], mark[N], t;
pll e[N];
vector<int> pth;
vector<int> vc[N];
vector<int> adj[N];

void dfs1(int u, int p) {
	vis[u] = 1;
	pth.push_back(u);
	bool flg = 0;
	bool flg2 = 0;
	for (int v:adj[u]) {
		if (!flg && v == p) {
			flg = 1;
			continue;
		}
		if (!vis[v]) {
			dfs1(v, u);
		}
		else if (!flg2 && vis[v] == 1) {
			flg2 = 1;
			int pt = (int)pth.size()-1;
			while (pth[pt] != v) {
				vc[t].push_back(pth[pt]);
				mark[pth[pt]] = 1;
				pt--;
			}
			vc[t].push_back(pth[pt]);
			mark[pth[pt]] = 1;
		}
	}
	pth.pop_back();
	vis[u] = 2;
}

void dfs2(int u, int p) {
	for (int v:adj[u]) {
		if (v == p || mark[v]) continue;
		dfs2(v, u);
		dp[u][1] += dp[v][0];
	}
	dp[u][0] = dp[u][1];
	for (int v:adj[u]) {
		if (v == p || mark[v]) continue;
		dp[u][0] = max(dp[u][0], dp[u][1] - dp[v][0] + dp[v][1] + 1);
	}
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		string s, t;
		cin >> s >> t;
		ll u = 0, v = 0;
		for (char c:s) {
			u = u*27 + (c-'a'+1);
		}
		for (char c:t) {
			v = v*27 + (c-'a'+1);
		}
		e[i] = {u, v};
	}
	if (n&1) {
		cout << -1 << endl;
		return;
	}
	sort(e+1, e+n+1);
	for (int u = 1; u <= n; u++) {
		int v = lower_bound(e+1, e+n+1, mk(e[u].S, 0ll))-e;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int u = 1; u <= n; u++) {
		if (!vis[u]) {
			t++;
			dfs1(u, 0);
		}
	}
	int ans = 0;
	for (int x = 1; x <= t; x++) {
		for (int u:vc[x]) {
			dfs2(u, 0);
		}
		if (vc[x].size() == 1) {
			ans += dp[vc[x][0]][0];
			continue;
		}
		if (vc[x].size() == 2) {
			int u = vc[x][0], v = vc[x][1];
			ans += max(dp[u][1] + dp[v][1] + 2, dp[u][0] + dp[v][0]);
			continue;
		}

		vc[x].push_back(vc[x][0]);
		int s = vc[x].size();
		int mx = 0;

		dp2[vc[x][0]][0] = 0;
		dp2[vc[x][0]][1] = -1e9;
		for (int i = 1; i < s; i++) {
			int u = vc[x][i];
			int v = vc[x][i-1];
			dp2[u][0] = max(dp2[v][0] + dp[v][0], dp2[v][1] + dp[v][1]);
			dp2[u][1] = dp2[v][0] + dp[v][1] + 1;
		}
		mx = max(mx, dp2[vc[x].back()][0]);

		dp2[vc[x][0]][0] = -1e9;
		dp2[vc[x][0]][1] = 0;
		for (int i = 1; i < s; i++) {
			int u = vc[x][i];
			int v = vc[x][i-1];
			dp2[u][0] = max(dp2[v][0] + dp[v][0], dp2[v][1] + dp[v][1]);
			dp2[u][1] = dp2[v][0] + dp[v][1] + 1;
		}
		mx = max(mx, dp2[vc[x].back()][1]);
		ans += mx;
	}
	cout << n-ans << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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