oj.uz

Submission #389481

# Submission time Handle Problem Language Result Execution time Memory
389481 2021-04-14T06:38:36 Z abc864197532 Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 32 ms 368 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 = 513, abc = 864197532;

int query(vector <int> islands);

int findEgg(int n, vector <pii> bridges) {
    vector <vector <int>> adj(n + 1);
    for (pii i : bridges) {
        adj[i.X].pb(i.Y);
        adj[i.Y].pb(i.X);
    }
    vector <bool> dead(n + 1, false);
    dead[0] = true;
    while (count(all(dead), false) > 1) {
        int cursz = count(all(dead), false);
        vector <int> cur;
        vector <bool> in(n + 1, false);
        int not_dead_cnt = 0;
        function<void(int, int)> dfs = [&](int v, int pa) {
            if (not_dead_cnt < cursz / 2) cur.pb(v), not_dead_cnt += !dead[v], in[v] = true;
            for (int u : adj[v]) if (u != pa) {
                dfs(u, v);
            }
        };
        dfs(1, -1);
        assert(not_dead_cnt == cursz / 2);
        int ans = query(cur);
        for (int i = 1; i <= n; ++i) if (!dead[i] && in[i] != ans) {
            dead[i] = true;
        }
    }
    for (int i = 1; i <= n; ++i) if (!dead[i]) {
        return i;
    }
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:23:36: warning: control reaches end of non-void function [-Wreturn-type]
   23 |     vector <vector <int>> adj(n + 1);
      |                                    ^

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Number of queries: 8
2 Correct 19 ms 328 KB Number of queries: 9
3 Correct 30 ms 340 KB Number of queries: 9
4 Correct 26 ms 332 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 368 KB Number of queries: 9
2 Correct 29 ms 332 KB Number of queries: 9
3 Correct 29 ms 344 KB Number of queries: 9
4 Correct 24 ms 328 KB Number of queries: 9