Submission #521936

#	Time	Username	Problem	Language	Result	Execution time	Memory
521936		boykut	Easter Eggs (info1cup17_eastereggs)	C++14	26.40 / 100	1025 ms	1568 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

int findEgg (int N, vector < pair < int, int > > bridges){
	vector<int> used(1 + N, 0);
	int LEN = N;
	for (int i = 1; i <= N; i++)
		used[i] = 1;
	while ((int)count(used.begin() + 1, used.end(), 1) > 0) {
		int oldC = count(used.begin() + 1, used.end(), 1);
		vector<vector<int>> g(1 + N);
		for (auto it : bridges) {
			int a, b;
			tie(a, b) = it;
			if (!used[a] || !used[b]) continue;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		if (LEN <= 2) {
			for (auto i = 1; i <= N; i++) {
				if (used[i])
					if (query({i}))
						return i;
			}
			//assert(false);
		}
		vector<int> heavy(1 + N, -1), comp;
		function<int(int, int)> dfs = [&](int v, int p) {
			int size = 1, mx_size = 0;
			for (auto to : g[v]) {
				if (to == p) continue;
				int c_size = dfs(to, v);
				size += c_size;
				if (c_size > mx_size) {
					mx_size = c_size;
					heavy[v] = to;
				}
			}
			return size;
		};
		function<void(int, int)> decompose = [&](int v, int p) {
			comp.push_back(v);
			if (heavy[v] != -1)
				decompose(heavy[v], v);
			for (auto to : g[v]) {
				if (to == p || to == heavy[v]) continue;
				decompose(to, v);
			}
		};
		deque<vector<int>> v;
		function<int(vector<int>)> check = [&](vector<int> comp) {
			vector<int> p(1 + N), s(1 + N), incomp(1 + N, 0);
			for (int i = 1; i <= N; i++) p[i] = i, s[i] = 1;
			function<int(int)> get = [&](int v) {
				return p[v] = (p[v] == v ? v : get(p[v]));
			};
			for (auto it : comp) incomp[it] = 1;
			for (auto it : bridges) {
				int a, b;
				tie(a, b) = it;
				if (!used[a] || !used[b]) continue;
				if (incomp[a] || incomp[b]) continue;
				if (get(a) != get(b)) {
					if (s[a] < s[b]) swap(a, b);
					s[a] += s[b];
					p[b] = a;
				}
			}
			int cnt = 0;
			for (int i = 1; i <= N; i++) {
				if (used[i] && !incomp[i]) cnt++;
			}
			return (cnt == s[get(1)] ? 1 : 0);
		};
		for (int s = 1; s <= N; s++) {
			if (!used[s]) continue;
			heavy.assign(1 + N, -1);
			comp.clear();
			dfs(s, -1);
			decompose(s, -1);
			if (check(comp)) {
				v.push_front(comp);
			} else {
				v.push_back(comp);
			}
		}
		if (v.empty()) assert(false);
		vector<int> Q;
		for (int i = 0; i < max(1, min((LEN+1)/2, (int)v[0].size())); i++)
			Q.push_back(v[0][i]);
		if (1 == query(Q)) {
			if (Q.size() == 1)
				return Q[0];
			vector<int> incomp(1 + N, 0);
			for (auto it : Q) incomp[it] = 1;
			for (int i = 1; i <= N; i++) {
				if (incomp[i] == 0 && used[i] == 1)
					used[i] = 0,
					LEN--;
			}
		} else {
			for (auto it : Q)
				used[it] = 0;
			LEN -= Q.size();
		}
		int C = count(used.begin() + 1, used.end(), 1);
		if (C == oldC) assert(false);
	}
	return -1;
}

• Subtask 1: 26.4 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20