제출 #821686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
821686		Pikachu	Easter Eggs (info1cup17_eastereggs)	C++17	10 / 100	223 ms	592 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int maxn = 520, oo = 1e9;
int n;
vector<int> adj[maxn];
bool era[maxn];
int dak, cur, cup;

int findEgg (int N, vector<pair<int,int> > bridges)
{
    memset(era, 0, sizeof era);
    ::n = N;
    for (int i = 1; i <= n; i++) adj[i].clear();
    for (pair<int,int> p : bridges) {
        adj[p.first].push_back(p.second);
        adj[p.second].push_back(p.first);
    }

    vector<int> rem(n);
    iota(rem.begin(), rem.end(), 1);
    while ((int)rem.size() > 1) {
        auto DFS = [&] (auto DFS, int u, int par) -> int
        {
            int cnt = 1;
            for (int v : adj[u]) {
                if (era[v]) continue;
                if (v == par) continue;
                cnt += DFS(DFS, v, u);
            }
            if (abs(dak - (int)rem.size() / 2) > abs(cnt - (int)rem.size() / 2)) {
                dak = cnt;
                cur = u;
                cup = par;
            }
            return cnt;
        };

        dak = oo;
        for (int x : rem) {
            DFS(DFS, x, -1);
        }

        vector<int> tmp;

        auto DFSadd = [&] (auto DFSadd, int u, int par) -> void
        {
            tmp.push_back(u);
            for (int v : adj[u]) {
                if (era[v]) continue;
                if (v != par) DFSadd(DFSadd, v, u);
            }
        };
        DFSadd(DFSadd, cur, cup);

        sort(tmp.begin(), tmp.end());
        if (!query(tmp)) {
            for (int x : tmp) era[x] = true;
            vector<int> newrem;
            for (int x : rem) {
                if (!era[x]) newrem.push_back(x);
            }
            swap(rem, newrem);
        }
        else {
            for (int x : rem) {
                if (!binary_search(tmp.begin(), tmp.end(), x)) era[x] = true;
            }
            swap(rem, tmp);
        }
    }

    return rem[0];
}

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