Submission #396683

#	Time	Username	Problem	Language	Result	Execution time	Memory
396683		Victor	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	27 ms	372 KiB

eastereggs

#include <bits/stdc++.h>

#include "grader.h"

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1000000007;

vi graph[513], vec;
uset<int> cands, chosen;
int take;

void choose(int u, int p) {
    if (!take) return;

    if (cands.count(u)) {
        --take;
        chosen.insert(u);
    }

    trav(v, graph[u]) if (v != p) choose(v, u);
}

bool dfs(int u, int p) {
    bool ret = chosen.count(u);
    trav(v, graph[u]) if (v != p) ret |= dfs(v, u);
    if (ret) vec.pb(u);
    return ret;
}

int recurse() {
    if (!sz(cands)) return 0;

    int root = *cands.begin();
    if (sz(cands) == 1) return root;

    chosen.clear();
    take = sz(cands) >> 1;
    choose(root, root);
    vec.clear();
    dfs(root, root);

    int egg = query(vec);

    if (!egg) {
        uset<int> next;
        trav(cand, cands) if (!chosen.count(cand)) next.insert(cand);
        chosen = next;
    }

    cands = chosen;

    return recurse();
}

int findEgg(int n, vii edges) {
    cands.clear();
    if (graph[1].empty())
        trav(edge, edges) {
            int u, v;
            tie(u, v) = edge;
            graph[u].pb(v);
            graph[v].pb(u);
        }
    rep(i, 0, n) cands.insert(i + 1);
    return recurse();
}

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