oj.uz

Submission #821686

# Submission time Handle Problem Language Result Execution time Memory
821686 2023-08-11T13:08:13 Z Pikachu Easter Eggs (info1cup17_eastereggs) C++17
10 / 100
 223 ms 592 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Number of queries: 4
2 Partially correct 1 ms 208 KB Number of queries: 5
3 Partially correct 1 ms 208 KB Number of queries: 9
4 Partially correct 1 ms 208 KB Number of queries: 15

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 208 KB Number of queries: 8
2 Partially correct 58 ms 208 KB Number of queries: 12
3 Partially correct 181 ms 340 KB Number of queries: 28
4 Runtime error 17 ms 460 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 356 KB Number of queries: 9
2 Partially correct 122 ms 336 KB Number of queries: 12
3 Partially correct 223 ms 336 KB Number of queries: 28
4 Runtime error 5 ms 592 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -