oj.uz

Submission #389311

# Submission time Handle Problem Language Result Execution time Memory
389311 2021-04-14T02:51:04 Z 2qbingxuan Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 22 ms 364 KB 
#include <bits/stdc++.h>
#include "grader.h"

#ifdef local
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define pary(a...) danb(#a, a)
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\033[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        std::cerr << (f++ ? ", " : "") << *L;
    std::cerr << " ]\033[0m\n";
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define pb emplace_back

using namespace std;
const int maxn = 525;

vector<int> g[maxn];
bool vis[maxn];
/*
int sz[maxn], mxCh[maxn];
void getSize(int i, int p = 0) {
    sz[i] = 1;
    mxCh[i] = -1;
    for (int j: g[i]) {
        if (j != p && !vis[j]) {
            getSize(j, i);
            sz[i] += sz[j];
            if (mxCh[i] == -1 || sz[mxCh[i]] < sz[j])
                mxCh[i] = j;
        }
    }
}
int findCent(int n, int i, int p = 0) {
    for (int j: g[i]) {
        if (j != p && !vis[j]) {
            if (sz[j] * 2 >= n)
                return findCent(n, j, i);
        }
    }
    return i;
}
void cd(int i) {
    getSize(i);
    int c = findCent(sz[i], i);
    vis[c] = true;
    if (mxCh[c] != -1) {
        dfs(mxCh[c]);
    }
}
*/
int findEgg (int N, vector < pair < int, int > > bridges) {
    for (int i = 1; i <= N; i++)
        g[i].clear(), vis[i] = 0;
    for (auto [a, b]: bridges) {
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    queue<int> q;
    vector<int> ord;
    vis[1] = true;
    q.push(1);
    while (!q.empty()) {
        int i = q.front(); q.pop();
        ord.emplace_back(i);
        debug(i);
        for (int j: g[i]) {
            if (!vis[j]) {
                vis[j] = true;
                q.push(j);
            }
        }
    }
    int pos = 0;
    for (int s = 1 << 20; s; s >>= 1) {
        if (pos + s >= N) continue;
        auto qq = vector<int>(ord.begin(), ord.begin() + pos + s);
        pary(all(qq));
        if (query(qq) == 0)
            pos += s;
    }
    return ord[pos];
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:66:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for (auto [a, b]: bridges) {
      |               ^

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 6 ms 328 KB Number of queries: 8
2 Correct 15 ms 356 KB Number of queries: 9
3 Correct 22 ms 364 KB Number of queries: 9
4 Correct 21 ms 328 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 328 KB Number of queries: 9
2 Correct 18 ms 364 KB Number of queries: 9
3 Correct 18 ms 352 KB Number of queries: 9
4 Correct 22 ms 328 KB Number of queries: 9