Submission #1347710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1347710		win	Easter Eggs (info1cup17_eastereggs)	C++20	In queue	0 ms	0 KiB

eastereggs

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

void dbg() { cout << "\n"; }
template<typename H, typename... T>
void dbg(H h, T... t) {
    cout << h << " ";
    dbg(t...);
}

const int N = 600;

int sz,mark[N],kuy[N];
vector<int> now,adj[N];
queue<int> qu;

int findEgg(int n, vector<pair<int,int>> e)
{
    for (int i = 1; i <= n; i++) now.push_back(i), kuy[i] = 1;
    for (auto x : e) {
        adj[x.first].push_back(x.second);
        adj[x.second].push_back(x.first);
    }
    sz = n;
    while (sz > 1) {
        memset(mark,0,sizeof(mark));
        vector<int> wow,tmp;
        int cnt = 1;
        qu.push(now[0]); mark[now[0]] = 1; wow.push_back(now[0]);
        while (!qu.empty()) {
            int top = qu.front(); qu.pop();
            if (cnt >= sz/2) continue;
            for (auto x : adj[top]) {
                if (mark[x] || !kuy[x] || cnt >= sz/2) continue;
                mark[x] = 1;
                qu.push(x);
                wow.push_back(x);
                cnt++;
            }
        }
        int ok = query(wow);
        if (ok) {
            for (auto x : now) {
                if (!mark[x]) continue;
                tmp.push_back(x);
            }
        } else {
            for (auto x : now) {
                if (mark[x]) continue;
                tmp.push_back(x);
            }
        }
        now.clear();
        for (auto x : tmp) now.push_back(x);
        sz = now.size();
    }
    return now[0];
}