Submission #952493

#TimeUsernameProblemLanguageResultExecution timeMemory
952493kilkuwuEaster Eggs (info1cup17_eastereggs)C++17
0 / 100
3 ms512 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "grader.h" #else using namespace std; int findEgg(int N, vector < pair < int, int > > bridges); int query(vector < int > islands); #endif int findEgg (int N, vector<pair<int, int>> bridges) { std::vector<std::vector<int>> adj(N + 1); for (auto bridge : bridges) { int u, v; std::tie(u, v) = bridge; adj[u].push_back(v); adj[v].push_back(u); } std::vector<int> maybe(N + 1, 1); // bfs and take half each time int num_candidates = N; while (num_candidates > 1) { std::vector<int> to_query; std::vector<int> inside(N + 1); int target = num_candidates / 2; std::function<void(int, int)> dfs = [&](int u, int p) -> void { to_query.push_back(u); target -= maybe[u]; inside[u] = 1; if (target == 0) { return; } for (int v : adj[u]) { if (v == p) continue; dfs(v, u); } }; dfs(1, 1); int res = query(to_query); if (res == 1) { num_candidates = 0; for (int i = 1; i <= N; i++) { if (!inside[i]) { maybe[i] = 0; } num_candidates += maybe[i]; } } else { num_candidates = 0; for (int i = 1; i <= N; i++) { if (inside[i]) { maybe[i] = 0; } num_candidates += maybe[i]; } } } for (int i = 1; i <= N; i++) { if (maybe[i]) return i; } assert(false); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...