Submission #1101242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101242		Kirill22	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	3 ms	592 KiB

eastereggs

#include "bits/stdc++.h"

using namespace std;

int query(vector < int > islands);

int findEgg(int N, vector<pair<int, int>> bridges) {
    vector<vector<int>> g(N);
    for (auto [x, y] : bridges) {
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vector<int> life(N, 1);
    while (std::count(life.begin(), life.end(), 1) > 1) {
        vector<int> _query;
        int m = std::count(life.begin(), life.end(), 1) / 2;
        vector<int> dp(N);
        auto dfs = [&] (auto&& self, int v, int pr) {
            if (!m) {
                return;
            }
            if (life[v]) {
                m--;
            }
            _query.push_back(v + 1);
            for (auto u : g[v]) {
                if (u != pr) {
                    self(self, u, v);
                }
            }
        };
        dfs(dfs, 0, 0);
        int res = query(_query);
        if (!res) {
            for (auto& v : _query) {
                life[v] = 0;
            }
        } else {
            for (int i = 0; i < N; i++) {
                if (std::count(_query.begin(), _query.end(), i) == 0) {
                    life[i] = 0;
                }
            }
        }
    }
    int ans = 0;
    while (!life[ans]) {
        ans++;
    }
    return ans + 1;
}

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20