| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1318855 | g31nius | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include <vector>
using namespace std;
int query(vector<int> islands); // Declaration of the grader's function
int findEgg(int N, vector<pair<int, int>> bridges) {
// Build adjacency list
vector<vector<int>> adj(N + 1);
for (auto& edge : bridges) {
adj[edge.first].push_back(edge.second);
adj[edge.second].push_back(edge.first);
}
// Binary search approach on the tree
// Start from node 1 and traverse the tree
int current = 1;
while (true) {
// Check each subtree of current node
bool found = false;
for (int neighbor : adj[current]) {
// Get all nodes in this subtree (excluding parent path)
vector<int> subtree;
vector<bool> visited(N + 1, false);
// DFS to collect subtree nodes
function<void(int, int)> dfs = [&](int node, int parent) {
visited[node] = true;
subtree.push_back(node);
for (int next : adj[node]) {
if (next != parent && !visited[next]) {
dfs(next, node);
}
}
};
dfs(neighbor, current);
// Query this subtree
if (query(subtree) == 1) {
current = neighbor;
found = true;
break;
}
}
// If no subtree contains the egg, it must be at current node
if (!found) {
return current;
}
}
}
