oj.uz

Submission #948855

# Submission time Handle Problem Language Result Execution time Memory
948855 2024-03-18T15:33:55 Z sysia Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 15 ms 1760 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "grader.h"
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef pair<int, int> T;
const int oo = 1e9+7;

int findEgg(int n, vector<T>edges){
    vector<vector<int>>g(n+1);
    for (auto [a, b]: edges){
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    vector<int>ord;
    function<void(int, int)>dfs = [&](int v, int pa){
        ord.emplace_back(v);
        for (auto x: g[v]){
            if (x == pa) continue;
            dfs(x, v);
        }
    };
    dfs(1, 1);
    debug(ord);
    int l = 0, r = n-2;
    int ans = n-1;
    while (r >= l){
        int m = (l+r)/2;
        vector<int>curr;
        for (int i = 0; i<=m; i++) curr.emplace_back(ord[i]);
        if (query(curr)) {
            ans = m;
            r = m-1;
        } else l = m+1;
    }
    return ord[ans];
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 736 KB Number of queries: 8
2 Correct 9 ms 724 KB Number of queries: 9
3 Correct 13 ms 500 KB Number of queries: 9
4 Correct 13 ms 1760 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1024 KB Number of queries: 9
2 Correct 12 ms 1244 KB Number of queries: 9
3 Correct 15 ms 736 KB Number of queries: 9
4 Correct 11 ms 744 KB Number of queries: 9