oj.uz

Submission #272802

# Submission time Handle Problem Language Result Execution time Memory
272802 2020-08-18T15:35:50 Z KayacanV Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 26 ms 384 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int nmax = (1 << 9) + 10;
 
bool query(vector < int > v);
 
int n, all[nmax];
vector < int > g[nmax];
 
void dfs(int node, int dad) {
    all[++n] = node;
    for (auto &it: g[node])
        if (it != dad) dfs(it, node);
}
 
bool do_query(int n) {
    vector < int > res;
    for (int i = 1; i <= n; ++i)
        res.push_back(all[i]);
    return query(res);
}
 
void clear_(int n) {
    for (int i = 1; i <= n; ++i)
        g[i].clear();
}
 
int findEgg(int dim, vector < pair < int, int > > edges) {
    clear_(dim);
    for (int i = 0; i < dim - 1; ++i) {
        int x, y; tie(x, y) = edges[i];
        g[x].push_back(y); g[y].push_back(x);
    }
 
    n = 0; dfs(1, 0);
 
    int left = 1; int right = n - 1; int res = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (do_query(mid) == 1)
            res = mid, right = mid - 1;
        else left = mid + 1;
    }
 
    res = all[res];
    return res;
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Number of queries: 8
2 Correct 17 ms 384 KB Number of queries: 9
3 Correct 20 ms 384 KB Number of queries: 9
4 Correct 17 ms 384 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 384 KB Number of queries: 9
2 Correct 16 ms 384 KB Number of queries: 9
3 Correct 23 ms 384 KB Number of queries: 9
4 Correct 23 ms 384 KB Number of queries: 9