Submission #1286590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286590		mihajlo0404	Easter Eggs (info1cup17_eastereggs)	C++20	Compilation error	0 ms	0 KiB

eastereggs

#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include "queue.h"
using namespace std;

// The signature of the query function (provided by the contest system)
// int query(vector<int> islands);

// Global structure to hold the tree for easy access in helper functions
map<int, vector<int>> adj;

// DFS to find all nodes in the subtree rooted at 'u' (when coming from 'p')
void get_subtree_nodes(int u, int p, vector<int>& subtree_nodes) {
    subtree_nodes.push_back(u);
    for (int v : adj[u]) {
        if (v != p) {
            get_subtree_nodes(v, u, subtree_nodes);
        }
    }
}

int findEgg(int N, vector<pair<int, int>> bridges) {
    // 1. Build the Adjacency List (Tree Structure)
    adj.clear();
    for (const auto& bridge : bridges) {
        adj[bridge.first].push_back(bridge.second);
        adj[bridge.second].push_back(bridge.first);
    }

    // 2. Start the Iterative Search
    int current_island = 1; // Start the search at island 1 (or any arbitrary node)
    int parent_island = 0;  // 0 represents a null/non-existent parent initially

    // The loop continues until the current_island is the egg's location
    while (true) {
        // Collect all neighbors (potential directions to move)
        vector<int> neighbors;
        for (int neighbor : adj[current_island]) {
            if (neighbor != parent_island) {
                neighbors.push_back(neighbor);
            }
        }

        // If no neighbors (other than the parent), the current_island is a leaf.
        // It must be the egg location if the search reached it.
        if (neighbors.empty()) {
            return current_island;
        }

        bool found_subtree = false;
        
        // 3. Query the Subtrees of all Neighbors
        for (int neighbor : neighbors) {
            vector<int> subtree_nodes;
            // Get all nodes in the subtree rooted at 'neighbor' 
            // (when coming from 'current_island')
            get_subtree_nodes(neighbor, current_island, subtree_nodes);

            if (query(subtree_nodes) == 1) {
                // Egg is in this subtree. Move the search to this neighbor.
                parent_island = current_island;
                current_island = neighbor;
                found_subtree = true;
                break; // Stop checking other subtrees and continue the loop
            }
        }

        // 4. Final Island Check
        if (!found_subtree) {
            // The egg was not found in any of the subtrees branching out.
            // Therefore, the egg must be at the current_island.
            return current_island;
        }
    }
}

Compilation message (stderr)

eastereggs.cpp:5:10: fatal error: queue.h: No such file or directory
    5 | #include "queue.h"
      |          ^~~~~~~~~
compilation terminated.