oj.uz

Submission #389300

# Submission time Handle Problem Language Result Execution time Memory
389300 2021-04-14T02:25:12 Z abc864197532 Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 344 ms 2708 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) { \
    for (auto a : x) cout << a << ' '; \
    cout << endl; \
}
#define pii pair<int, int>
#define pll pair<lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int N = 512, abc = 864197532;

vector <int> adj[N];

int query(vector <int> islands);

int findEgg(int n, vector <pii> bridges) {
    for (pii i : bridges) {
        adj[--i.X].pb(--i.Y);
        adj[i.Y].pb(i.X);
    }
    vector <bool> dead(n, false);
    while (true) {
        vector <vector <int>> sz(n, vector <int>(n, 1));
        function<void(int, int, int)> dfs1 = [&](int v, int pa, int rt) {
            for (int u : adj[v]) if (u != pa && !dead[u]) {
                dfs1(u, v, rt);
                sz[rt][v] += sz[rt][u];
            }
        };
        pii best;
        for (int i = 0; i < n; ++i) if (!dead[i]) {
            dfs1(i, -1, i);
            for (int j = 0; j < n; ++j) if (!dead[j]) {
                if (max(n - sz[best.X][best.Y], sz[best.X][best.Y]) < max(n - sz[i][j], sz[i][j])) {
                    best = mp(i, j);
                }
            }
        }
        vector <int> island;
        function<void(int, int, bool)> dfs2 = [&](int v, int pa, bool is) {
            if (v == best.Y) is = true;
            if (is) island.pb(v + 1);
            for (int u : adj[v]) if (u != pa) {
                dfs2(u, v, is);
            }
        };
        dfs2(best.X, -1, false);
        int ans = query(island);
        if (ans) {
            for (int i = 0; i < n; ++i) if (!count(all(island), i)) {
                dead[i] = true;
            }
        } else {
            for (int i = 0; i < n; ++i) if (count(all(island), i)) {
                dead[i] = true;
            }
        }
        n = count(all(dead), false);
        if (n == 1) {
            for (int i = 0; i < n; ++i) if (!dead[i]) {
                return i + 1;
            }
        }
    }
}

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 Runtime error 69 ms 988 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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