oj.uz

Submission #396683

# Submission time Handle Problem Language Result Execution time Memory
396683 2021-04-30T15:12:01 Z Victor Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 27 ms 372 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 304 KB Number of queries: 4
2 Correct 1 ms 200 KB Number of queries: 4
3 Correct 2 ms 200 KB Number of queries: 4
4 Correct 2 ms 200 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 328 KB Number of queries: 8
2 Correct 19 ms 328 KB Number of queries: 9
3 Correct 23 ms 328 KB Number of queries: 9
4 Correct 21 ms 368 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 328 KB Number of queries: 9
2 Correct 27 ms 372 KB Number of queries: 9
3 Correct 24 ms 328 KB Number of queries: 9
4 Correct 24 ms 328 KB Number of queries: 9