Submission #521947

#	Time	Username	Problem	Language	Result	Execution time	Memory
521947		boykut	Easter Eggs (info1cup17_eastereggs)	C++14	26.40 / 100	23 ms	468 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 <= 4) {
			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);
			}
		};
		vector<int> v;
		for (int s = 1; s <= N; s++) {
			if (!used[s]) continue;
			heavy.assign(1 + N, -1);
			comp.clear();
			dfs(s, -1);
			decompose(s, -1);
			v = comp;
			break;
		}
		vector<int> Q;
		for (int i = 0; i < max(1, min(LEN / 2, (int)v.size())); i++)
			Q.push_back(v[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--;
		}
		int C = count(used.begin() + 1, used.end(), 1);
		//if (C == oldC) assert(false);
	}
	return -1;
}

Compilation message (stderr)

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:12:7: warning: unused variable 'oldC' [-Wunused-variable]
   12 |   int oldC = count(used.begin() + 1, used.end(), 1);
      |       ^~~~
eastereggs.cpp:80:7: warning: unused variable 'C' [-Wunused-variable]
   80 |   int C = count(used.begin() + 1, used.end(), 1);
      |       ^

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