Submission #373707

#	Time	Username	Problem	Language	Result	Execution time	Memory
373707		luciocf	Love Polygon (BOI18_polygon)	C++14	75 / 100	343 ms	15348 KiB

polygon

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int f[maxn];

int nivel[maxn], cc;
int ini[maxn], fim[maxn];
int mark[maxn];

bool done[maxn], incycle[maxn];

void dfs(int u)
{
	mark[u] = 1;

	if (mark[f[u]] == 1)
	{
		++cc;
		mark[u] = 2;
		ini[cc] = f[u], fim[cc] = u;
		return;
	}

	if (!mark[f[u]]) dfs(f[u]);

	nivel[u] = nivel[f[u]]+1;
	mark[u] = 2;
}

bool comp(int a, int b)
{
	if (incycle[a] && !incycle[b]) return 0;
	if (!incycle[a] && incycle[b]) return 1;
	return nivel[a] > nivel[b];
}

int main(void)
{
	int n;
	cin >> n;

	map<string, int> mp;

	int ind = 0;

	for (int i = 1; i <= n; i++)
	{
		string s1, s2;
		cin >> s1 >> s2;

		if (mp.find(s1) == mp.end()) mp[s1] = ++ind;
		if (mp.find(s2) == mp.end()) mp[s2] = ++ind;

		f[mp[s1]] = mp[s2];
	}

	if (n&1)
	{
		cout << "-1\n";
		return 0;
	}

	for (int i = 1; i <= n; i++)
		if (!mark[i])
			dfs(i);

	int ans = n;

	vector<int> v;
	for (int i = 1; i <= n; i++)
		v.push_back(i);

	for (int i = 1; i <= cc; i++)
	{
		for (int u = ini[i]; ; u = f[u])
		{
			incycle[u] = 1;
			if (u == fim[i]) break;
		}
	}

	sort(v.begin(), v.end(), comp);

	for (int i = 1; i <= n; i++)
	{
		if (done[i]) continue;
		
		if (f[i] != i && f[f[i]] == i)
		{
			done[i] = done[f[i]] = 1;
			ans -= 2;
		}
	}

	for (auto u: v)
	{
		if (done[u]) continue;

		if (f[u] != u && !done[f[u]])
		{
			ans--;
			done[u] = done[f[u]] = 1;
		}
	}

	cout << ans << "\n";
}

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