oj.uz

Submission #170874

# Submission time Handle Problem Language Result Execution time Memory
170874 2019-12-26T16:08:24 Z nobik Split the Attractions (IOI19_split) C++14
46 / 100
 258 ms 24040 KB 
#include "split.h"
#include <bits/stdc++.h>

using namespace std;

struct Fau {
	int n;

	vector<int> parent;
	vector<vector<int>> bucket;

	Fau(int n): n(n), parent(n), bucket(n) {
		for (int i = 0; i < n; ++i) {
			bucket[i].push_back(i);
			parent[i] = i;
		}
	}

	int Root(int a) {
		return parent[a] == a ? a : Root(parent[a]);
	}

	int Union(int a, int b) {
		a = Root(a);
		b = Root(b);
		if (a == b)
			return a;
		
		if (bucket[a].size() > bucket[b].size())
			swap(a, b);
		
		parent[a] = b;
		bucket[b].insert(bucket[b].end(), bucket[a].begin(), bucket[a].end());
		bucket[a].clear();
		bucket[a].shrink_to_fit();

		return b;
	}

	int Size(int v) {
		return (int) bucket[v].size();
	}
};

struct Solver {
	int n, m;

	vector<vector<pair<int, int>>> graph;
	vector<int> tree_edges;
	vector<int> used, sizes;

	vector<pair<int, int>> component_sizes;

	Solver(int n, const vector<pair<int, int>>& edges, int a, int b, int c)
			: n(n), m(edges.size()), graph(n), tree_edges(m), used(n), sizes(n) {
		component_sizes.emplace_back(a, 1);
		component_sizes.emplace_back(b, 2);
		component_sizes.emplace_back(c, 3);
		sort(component_sizes.begin(), component_sizes.end());

		for (int i = 0; i < m; ++i) {
			int x = edges[i].first, y = edges[i].second;
			graph[x].emplace_back(y, i);
			graph[y].emplace_back(x, i);
		}
	}

	void FindSpanningTree(int v) {
		used[v] = 1;
		sizes[v] = 1;
		for (const auto& edge: graph[v]) {
			int to = edge.first, id = edge.second;
			if (used[to])
				continue;
			
			tree_edges[id] = 1;
			FindSpanningTree(to);
			sizes[v] += sizes[to];
		}
	}

	int FindCentroid(int v, int parent) {
		for (const auto& edge: graph[v]) {
			int to = edge.first, id = edge.second;
			if (to == parent || !tree_edges[id])
				continue;
			
			if (2 * sizes[to] > n)
				return FindCentroid(to, v);
		}

		return v;
	}

	void UniteSubtrees(int centroid, Fau& fau) {
		for (int i = 0; i < n; ++i) {
			if (i == centroid)
				continue;
			
			for (const auto& edge: graph[i]) {
				int to = edge.first, id = edge.second;
				if (to == centroid || !tree_edges[id])
					continue;
				
				fau.Union(i, to);
			}
		}
	}

	vector<int> Solve() {
		FindSpanningTree(0);
		int centroid = FindCentroid(0, -1);

		Fau fau(n);
		UniteSubtrees(centroid, fau);

		
		int max_subtree_vertex = -1, max_subtree_size = -1;
		for (int i = 0; i < n; ++i) {
			if (fau.Root(i) == i && fau.Size(i) > max_subtree_size) {
				max_subtree_size = fau.Size(i);
				max_subtree_vertex = i;
			}
		}

		for (int i = 0; i < n; ++i) {
			if (i == centroid)
				continue;
			
			for (const auto& edge: graph[i]) {
				if (max_subtree_size >= component_sizes[0].first)
					break;
				
				int to = edge.first;
				if (to == centroid)
					continue;
				
				int vertex = fau.Union(i, to);
				if (fau.Size(vertex) > max_subtree_size) {
					max_subtree_size = fau.Size(vertex);
					max_subtree_vertex = vertex;
				}
			}
		}

		// Solution was not found!
		if (max_subtree_size < component_sizes[0].first) {
			return vector<int>(n);
		}

		vector<int> result(n, component_sizes.back().second);
		Color(max_subtree_vertex, fau.bucket[max_subtree_vertex], component_sizes[0].first, component_sizes[0].second, result);
		Color(centroid, Complement(fau.bucket[max_subtree_vertex]), component_sizes[1].first, component_sizes[1].second, result);
		return result;
	}

	void Color(int v, const vector<int>& allowed_vertices, int size, int color, vector<int>& colors) {
		vector<int> used(n, 1);
		for (int e: allowed_vertices)
			used[e] = 0;

		queue<int> q;
		q.push(v);
		used[v] = 1;

		while (!q.empty() && size > 0) {
			v = q.front();
			q.pop();
			colors[v] = color;
			--size;

			for (const auto& edge: graph[v]) {
				int to = edge.first;
				if (!used[to]) {
					q.push(to);
					used[to] = 1;
				}
			}
		}
	}

	vector<int> Complement(const vector<int>& a) {
		vector<int> b(n), result;
		for (int e: a) b[e] = 1;
		for (int i = 0; i < n; ++i) {
			if (!b[i])
				result.push_back(i);
		}

		return result;
	}
};

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m = static_cast<int>(p.size());
	vector<pair<int, int>> edges;
	for (int i = 0; i < m; ++i) {
		edges.emplace_back(p[i], q[i]);
	}

	Solver solver(n, edges, a, b, c);
	return solver.Solve();
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB invalid split: #1=0, #2=1, #3=2
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 256 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 167 ms 21776 KB ok, correct split
5 Correct 133 ms 17648 KB ok, correct split
6 Correct 145 ms 20204 KB ok, correct split
7 Correct 136 ms 18924 KB ok, correct split
8 Correct 258 ms 24040 KB ok, correct split
9 Correct 186 ms 16492 KB ok, correct split
10 Incorrect 89 ms 18412 KB invalid split: #1=0, #2=49999, #3=50000
11 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 139 ms 17772 KB ok, correct split
3 Correct 45 ms 7868 KB ok, correct split
4 Correct 2 ms 256 KB ok, correct split
5 Correct 146 ms 17644 KB ok, correct split
6 Correct 138 ms 17516 KB ok, correct split
7 Correct 135 ms 17488 KB ok, correct split
8 Correct 132 ms 18156 KB ok, correct split
9 Correct 151 ms 17644 KB ok, correct split
10 Correct 39 ms 6000 KB ok, no valid answer
11 Correct 58 ms 8944 KB ok, no valid answer
12 Correct 110 ms 17776 KB ok, no valid answer
13 Correct 142 ms 18192 KB ok, no valid answer
14 Correct 80 ms 17540 KB ok, no valid answer

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 2 ms 256 KB ok, no valid answer
3 Correct 2 ms 256 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 256 KB ok, correct split
7 Correct 2 ms 380 KB ok, correct split
8 Correct 2 ms 376 KB ok, correct split
9 Correct 5 ms 888 KB ok, correct split
10 Correct 6 ms 964 KB ok, correct split
11 Correct 2 ms 376 KB ok, correct split
12 Correct 6 ms 888 KB ok, correct split
13 Correct 2 ms 376 KB ok, correct split
14 Correct 2 ms 376 KB ok, correct split
15 Correct 2 ms 376 KB ok, correct split
16 Correct 2 ms 376 KB ok, correct split
17 Correct 2 ms 376 KB ok, correct split
18 Correct 2 ms 376 KB ok, correct split
19 Correct 2 ms 376 KB ok, correct split
20 Correct 3 ms 504 KB ok, correct split
21 Correct 4 ms 760 KB ok, correct split
22 Correct 4 ms 760 KB ok, correct split
23 Correct 4 ms 760 KB ok, correct split
24 Correct 4 ms 760 KB ok, correct split
25 Correct 4 ms 848 KB ok, correct split
26 Correct 4 ms 812 KB ok, correct split
27 Correct 5 ms 888 KB ok, correct split
28 Correct 3 ms 888 KB ok, correct split
29 Correct 2 ms 376 KB ok, correct split
30 Correct 5 ms 888 KB ok, correct split
31 Correct 3 ms 504 KB ok, correct split
32 Correct 2 ms 376 KB ok, correct split
33 Correct 3 ms 376 KB ok, correct split
34 Correct 5 ms 760 KB ok, correct split
35 Correct 5 ms 888 KB ok, correct split
36 Correct 4 ms 760 KB ok, correct split
37 Correct 5 ms 1016 KB ok, correct split
38 Correct 5 ms 888 KB ok, correct split
39 Correct 5 ms 888 KB ok, correct split
40 Correct 5 ms 888 KB ok, correct split
41 Correct 3 ms 632 KB ok, correct split
42 Correct 4 ms 632 KB ok, correct split
43 Correct 5 ms 888 KB ok, correct split
44 Correct 5 ms 888 KB ok, correct split
45 Correct 5 ms 888 KB ok, correct split
46 Correct 4 ms 760 KB ok, correct split
47 Correct 4 ms 764 KB ok, no valid answer
48 Correct 4 ms 760 KB ok, correct split
49 Correct 4 ms 888 KB ok, correct split
50 Correct 2 ms 376 KB ok, no valid answer
51 Correct 2 ms 256 KB ok, no valid answer
52 Correct 4 ms 760 KB ok, no valid answer
53 Correct 5 ms 888 KB ok, no valid answer
54 Correct 4 ms 760 KB ok, no valid answer
55 Correct 4 ms 760 KB ok, no valid answer
56 Correct 4 ms 760 KB ok, no valid answer

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB invalid split: #1=0, #2=1, #3=2
2 Halted 0 ms 0 KB -