oj.uz

Submission #373716

# Submission time Handle Problem Language Result Execution time Memory
373716 2021-03-05T13:48:23 Z luciocf Love Polygon (BOI18_polygon) C++14
25 / 100
 354 ms 15976 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int f[maxn];

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

bool done[maxn], done2[maxn], incycle[maxn];

vector<int> all[maxn];

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

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

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

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

int solve_ciclo(int c)
{
	if (f[fim[c]] == fim[c]) return 0;

	for (int u = ini[c]; ; u = f[u])
	{
		done2[u] = done[u];
		if (u == fim[c]) break;
	}

	int ans = 0;

	if (f[ini[c]] == fim[c]) ans += 2;
	else ans++;

	done2[ini[c]] = done2[fim[c]] = 1;

	for (auto u: all[c])
	{
		if (done2[u]) continue;

		if (f[u] != u && !done2[f[u]])
		{
			ans++;
			done2[u] = done2[f[u]] = 1;
		}
	}

	return ans;
}

int solve_nociclo(int c)
{
	for (int u = ini[c]; ; u = f[u])
	{
		done2[u] = done[u];
		if (u == fim[c]) break;
	}

	int ans = 0;

	for (auto u: all[c])
	{
		if (done2[u]) continue;

		if (f[u] != u && !done2[f[u]])
		{
			ans++;
			done2[u] = done2[f[u]] = 1;
		}
	}

	return ans;
}

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);

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

	int ans = n;

	vector<int> v;
	for (int i = 1; i <= n; i++)
	{
		if (!incycle[i] && !incycle[f[i]])
			v.push_back(i);
		else
			all[comp[i]].push_back(i);
	}

	sort(v.begin(), v.end(), [&](int a, int b) {return nivel[a] > nivel[b];});

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

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

	for (int c = 1; c <= cc; c++)
	{
		sort(all[c].begin(), all[c].end(), [&](int a, int b) {return nivel[a] > nivel[b];});
		ans -= max(solve_ciclo(c), solve_nociclo(c));
	}

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

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Incorrect 2 ms 2668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 354 ms 15748 KB Output is correct
5 Correct 309 ms 13420 KB Output is correct
6 Correct 345 ms 15976 KB Output is correct
7 Correct 292 ms 10860 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 301 ms 13064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Incorrect 2 ms 2668 KB Output isn't correct
4 Halted 0 ms 0 KB -