oj.uz

Submission #374769

# Submission time Handle Problem Language Result Execution time Memory
374769 2021-03-08T06:41:38 Z Alex_tz307 Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 28 ms 512 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int NMAX = 515;
vector<int> G[NMAX], dfs_pref;

void dfs(int u, int parent) {
    dfs_pref.emplace_back(u);
    for(const int &v : G[u])
        if(v != parent)
            dfs(v, u);
}

void Clear(int N) {
    for(int u = 1; u <= N; ++u)
        G[u].clear();
    dfs_pref.clear();
    dfs_pref.emplace_back(0);
}

bool check(int poz) {
    vector<int> ask;
    for(int i = 1; i <= poz; ++i)
        ask.emplace_back(dfs_pref[i]);
    return query(ask);
}

int findEgg(int N, vector<pair<int,int>> bridges) {
    Clear(N);
    for(int i = 0; i < N - 1; ++i) {
        int u, v;
        tie(u, v) = bridges[i];
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1, 0);
    int st = 1, dr = N - 1, ans = N;
    while(st <= dr) {
        int mid = (st + dr) >> 1;
        if(check(mid)) {
            ans = mid;
            dr = mid - 1;
        }
        else
            st = mid + 1;
    }
    return dfs_pref[ans];
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 364 KB Number of queries: 8
2 Correct 18 ms 512 KB Number of queries: 9
3 Correct 21 ms 364 KB Number of queries: 9
4 Correct 17 ms 424 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 364 KB Number of queries: 9
2 Correct 19 ms 364 KB Number of queries: 9
3 Correct 21 ms 364 KB Number of queries: 9
4 Correct 19 ms 364 KB Number of queries: 9