oj.uz

Submission #396681

# Submission time Handle Problem Language Result Execution time Memory
396681 2021-04-30T15:11:17 Z Victor Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 400 ms 456 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();
    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
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 456 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 328 KB Time limit exceeded
2 Halted 0 ms 0 KB -