oj.uz

Submission #403580

# Submission time Handle Problem Language Result Execution time Memory
403580 2021-05-13T09:44:53 Z hltk Easter Eggs (info1cup17_eastereggs) C++17
10 / 100
 400 ms 380 KB 
#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
// int query(vector<int> islands) {
// 	cout << "query({";
// 	bool f = 1;
// 	for (int u : islands) {
// 		if (!f) cout << ", ";
// 		f = 0;
// 		cout << u;
// 	}
// 	cout << "}): ";
// 	int x;
// 	cin >> x;
// 	return x;
// }
int findEgg(int n, vector<pair<int, int>> bridges) {
	vector<vector<int>> g(n + 1);
	for (auto [a, b] : bridges) {
		g[a].push_back(b);
		g[b].push_back(a);
	}
	set<int> opts;
	for (int i = 1; i <= n; ++i) opts.insert(i);
	while (opts.size() > 1) {
		int bdiff = 1e9, eid = -1;
		for (int i = 0; i < (int) bridges.size(); ++i) {
			int a = bridges[i].first, b = bridges[i].second;
			if (!opts.count(a) || !opts.count(b)) continue;
			function<int(int, int)> dfs = [&](int v, int p) {
				int r = 1;
				for (auto u : g[v]) {
					if (minmax(v, u) == minmax(a, b)) continue;
					if (!opts.count(u) || u == p) continue;
					r += dfs(u, v);
				}
				return r;
			};
			int ax = dfs(a, -1);
			int bx = dfs(b, -1);
			if (int off = abs(ax - bx); off < bdiff) {
				bdiff = off;
				eid = i;
			}
		}
		int a = bridges[eid].first, b = bridges[eid].second;
		function<set<int>(int, int)> dfs = [&](int v, int p) {
			set ret{v};
			for (auto u : g[v]) {
				if (minmax(v, u) == minmax(a, b)) continue;
				if (!opts.count(u) || u == p) continue;
				ret.merge(dfs(u, v));
			}
			return ret;
		};
		auto o = dfs(a, -1);
		if (query({o.begin(), o.end()})) {
			auto z = opts;
			for (auto u : z) {
				if (!o.count(u)) {
					opts.erase(u);
				}
			}
		} else {
			for (auto u : o) {
				opts.erase(u);
			}
		}
	}
	assert(opts.size() == 1);
	return *opts.begin();
}
// int main() {
// 	int ret = findEgg(5, {{1, 2}, {1, 3}, {2, 4}, {4, 5}});
// 	cout << "findEgg: " << ret << endl;
// }

Subtask #1
10.0 / 40.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 328 KB Number of queries: 8
2 Execution timed out 884 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2427 ms 380 KB Time limit exceeded
2 Halted 0 ms 0 KB -