Submission #521909

#	Time	Username	Problem	Language	Result	Execution time	Memory
521909		boykut	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	15 ms	516 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) {
		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 <= 3) {
			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 (comp.size() > LEN / 2) return;
			if (heavy[v] != -1)
				decompose(heavy[v], v);
			for (auto to : g[v]) {
				if (to == p || to == heavy[v]) continue;
				decompose(to, v);
				if (comp.size() > LEN / 2) return;
			}
		};
		vector<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_back(comp);
			}
		}
		if (v.empty()) assert(false);
		if (1 == query(v[0])) {
			if (v[0].size() == 1)
				return v[0][0];
			vector<int> incomp(1 + N, 0);
			for (auto it : v[0]) 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 : v[0])
				used[it] = 0;
			LEN -= v[0].size();
		}
	}
	return -1;
}

Compilation message (stderr)

eastereggs.cpp: In lambda function:
eastereggs.cpp:44:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |    if (comp.size() > LEN / 2) return;
      |        ~~~~~~~~~~~~^~~~~~~~~
eastereggs.cpp:50:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |     if (comp.size() > LEN / 2) return;
      |         ~~~~~~~~~~~~^~~~~~~~~

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