Submission #948855

#	Time	Username	Problem	Language	Result	Execution time	Memory
948855		sysia	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	15 ms	1760 KiB

eastereggs

//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 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20