oj.uz

Submission #373714

# Submission time Handle Problem Language Result Execution time Memory
373714 2021-03-05T13:46:11 Z luciocf Love Polygon (BOI18_polygon) C++14
75 / 100
 337 ms 17640 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], 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;

	int ans = 0;

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

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

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

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

	return ans;
}

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

	int ans = 0;

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

		if (f[u] != u && !done[f[u]])
		{
			ans++;
			done[u] = done[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
21.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 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 328 ms 17384 KB Output is correct
5 Correct 337 ms 15028 KB Output is correct
6 Correct 324 ms 17640 KB Output is correct
7 Correct 314 ms 12704 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 14568 KB Output is correct
2 Correct 322 ms 15080 KB Output is correct
3 Correct 267 ms 17516 KB Output is correct
4 Correct 304 ms 12672 KB Output is correct
5 Correct 314 ms 15592 KB Output is correct
6 Correct 316 ms 14504 KB Output is correct
7 Correct 303 ms 14568 KB Output is correct
8 Correct 328 ms 16108 KB Output is correct
9 Correct 297 ms 14488 KB Output is correct
10 Correct 251 ms 14568 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct

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 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 2 ms 2796 KB Output is correct
17 Correct 3 ms 2668 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct
19 Correct 328 ms 17384 KB Output is correct
20 Correct 337 ms 15028 KB Output is correct
21 Correct 324 ms 17640 KB Output is correct
22 Correct 314 ms 12704 KB Output is correct
23 Correct 324 ms 14568 KB Output is correct
24 Correct 322 ms 15080 KB Output is correct
25 Correct 267 ms 17516 KB Output is correct
26 Correct 304 ms 12672 KB Output is correct
27 Correct 314 ms 15592 KB Output is correct
28 Correct 316 ms 14504 KB Output is correct
29 Correct 303 ms 14568 KB Output is correct
30 Correct 328 ms 16108 KB Output is correct
31 Correct 297 ms 14488 KB Output is correct
32 Correct 251 ms 14568 KB Output is correct
33 Correct 2 ms 2668 KB Output is correct
34 Correct 2 ms 2668 KB Output is correct
35 Correct 2 ms 2668 KB Output is correct
36 Correct 2 ms 2668 KB Output is correct
37 Correct 323 ms 14568 KB Output is correct
38 Incorrect 323 ms 15208 KB Output isn't correct
39 Halted 0 ms 0 KB -