Submission #520656

#	Time	Username	Problem	Language	Result	Execution time	Memory
520656		Sohsoh84	Love Polygon (BOI18_polygon)	C++17	100 / 100	309 ms	79256 KiB

polygon

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;

int n, dp[MAXN][2], ans, deg[MAXN];
bool vis[MAXN], in_cyc[MAXN];
vector<int> cyc, adj[MAXN], adj_r[MAXN], cmp;
vector<pair<string, string>> vec;
map<string, int> mp;
queue<int> q;

void dfs_cmp(int v) {
	vis[v] = true;
	cmp.push_back(v);
	in_cyc[v] = true;
	if (deg[v] == 0) {
		in_cyc[v] = false;
		q.push(v);
	}

	for (int u : adj[v])
		if (!vis[u])
			dfs_cmp(u);

	for (int u : adj_r[v])
		if (!vis[u])
			dfs_cmp(u);
}

void dfs_cyc(int v, int root) {
	cyc.push_back(v);
	for (int u : adj[v])
		if (in_cyc[u] && u != root)
			dfs_cyc(u, root);
}

inline void find_cyc(int v) {
	cmp.clear();
	cyc.clear();

	dfs_cmp(v);
	while (!q.empty()) {
		int v = q.front();
		q.pop();

		for (int u : adj_r[v]) {
			deg[u]--;
			if (deg[u] == 0) {
				in_cyc[u] = false;
				q.push(u);
			}
		}
	}

	for (int v : cmp) {
		if (in_cyc[v]) {
			dfs_cyc(v, v);
			break;
		}
	}
}

void dfs(int v, int p) {
	int delta = 0;

	for (int u : adj[v]) {
		if (u == p || in_cyc[u]) continue;
		dfs(u, v);

		dp[v][0] += dp[u][1];
		dp[v][1] += dp[u][1];
		delta = max(delta, dp[u][0] - dp[u][1] + 1);
	}
	
	dp[v][1] += delta;
}

inline int calc() {
	int f[2] = {-1, 0};
	for (int v : cyc) {
		int d0 = f[1] + dp[v][0];
		f[1] = max({d0, dp[v][1] + f[1], dp[v][0] + f[0] + 1});
		f[0] = d0;
	}

	return f[1];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	if (n & 1) return cout << -1 << endl, 0;

	ans = n;
	
	for (int i = 0; i < n; i++) {
		string a, b;
		cin >> a >> b;
		mp[a] = i + 1;
		vec.push_back({a, b});
	}

	for (auto e : vec) {
		int u = mp[e.Y], v = mp[e.X];
		adj[u].push_back(v);
		adj_r[v].push_back(u);
		deg[u]++;
	}

	for (int t = 1; t <= n; t++) {
		if (vis[t]) continue;
		find_cyc(t);

		for (int v : cyc)
			dfs(v, 0);

		if (cyc.size() == 1) ans -= dp[cyc[0]][1];
		else if (cyc.size() == 2) ans -= dp[cyc[0]][0] + dp[cyc[1]][0] + 2;
		else {
			int tans = calc();
			cyc.insert(cyc.begin(), cyc.back());
			cyc.pop_back();
			ans -= max(tans, calc());
		}	
	}

	cout << ans << endl;
	return 0;
}

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