제출 #1139140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139140		stdfloat	Easter Eggs (info1cup17_eastereggs)	C++20	26.40 / 100	5 ms	460 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
// #include "grader.cpp"
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int rnd(int l, int r) {
    return l + rng() % (r - l + 1);
}

int findEgg (int n, vector<pair<int, int>> brg){
    vector<int> E[n + 1];
    for (int i = 0; i < n - 1; i++) {
        auto [x, y] = brg[i];

        E[x].push_back(y);
        E[y].push_back(x);
    }

    vector<bool> vis(n + 1);
    while (true) {
        int x = -1, cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) {
                x = i;
                cnt++;
            }
        }

        if (cnt == 1) return x;

        vector<int> v;
        queue<int> q;
        vector<bool> visq(n + 1);
        q.push(x); visq[x] = true;
        while (!q.empty() && (int)v.size() < (cnt >> 1)) {
            int x = q.front(); q.pop();

            v.push_back(x);
            for (auto i : E[x]) {
                if (!vis[i] && !visq[i]) {
                    q.push(i);
                    visq[i] = true;
                }
            }
        }

        visq.assign(n + 1, false);
        for (auto i : v)
            visq[i] = true;

        bool tr = query(v);
        for (int i = 1; i <= n; i++)
            if (!vis[i]) vis[i] = (tr ? !visq[i] : visq[i]);
    }
}

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