oj.uz

Submission #521948

# Submission time Handle Problem Language Result Execution time Memory
521948 2022-02-03T13:39:51 Z boykut Easter Eggs (info1cup17_eastereggs) C++14
26.4 / 100
 26 ms 456 KB 
#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 <= 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);
			dfs(s, -1);
			decompose(s, -1);
			v = comp;
			break;
		}
		if (v.empty()) return 0;
		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--;
		}
	}
	return -1;
}

Subtask #1
26.4 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 200 KB Number of queries: 6
2 Partially correct 1 ms 200 KB Number of queries: 6
3 Partially correct 1 ms 200 KB Number of queries: 7
4 Partially correct 1 ms 200 KB Number of queries: 9

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 328 KB Number of queries: 10
2 Partially correct 11 ms 328 KB Number of queries: 29
3 Partially correct 26 ms 328 KB Number of queries: 29
4 Runtime error 2 ms 456 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 21 ms 400 KB Number of queries: 12
2 Partially correct 21 ms 328 KB Number of queries: 28
3 Partially correct 22 ms 328 KB Number of queries: 29
4 Runtime error 2 ms 456 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -