oj.uz

Submission #389285

# Submission time Handle Problem Language Result Execution time Memory
389285 2021-04-14T02:13:56 Z cheissmart Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 27 ms 480 KB 
#include <bits/stdc++.h>
#include "grader.h"
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << "): " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 520;

V<int> G[N];
vi q;

void init(int n) {
    for(int i = 1; i <= n; i++) {
        G[i].clear();
    }
}

void dfs(int u, int p = 0) {
    q.PB(u);
    for(int v:G[u]) if(v != p)
        dfs(v, u);
}

int findEgg(int n, V<pi> es) {
    init(n);
    for(pi p:es) G[p.F].PB(p.S), G[p.S].PB(p.F);
    q.clear();
    dfs(1);
    int lb = 0, rb = n - 2;
    while(lb <= rb) {
        int mb = (lb + rb) / 2;
        vi ask;
        for(int j = 0; j <= mb; j++)
            ask.PB(q[j]);
        if(query(ask)) rb = mb - 1;
        else lb = mb + 1;
    }
    //debug(lb);
    return q[lb];
}

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 204 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 336 KB Number of queries: 8
2 Correct 16 ms 344 KB Number of queries: 9
3 Correct 23 ms 348 KB Number of queries: 9
4 Correct 21 ms 356 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 356 KB Number of queries: 9
2 Correct 19 ms 480 KB Number of queries: 9
3 Correct 27 ms 344 KB Number of queries: 9
4 Correct 18 ms 352 KB Number of queries: 9