제출 #1288673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288673		al95ireyiz	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	512 KiB

eastereggs

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll INF = 1e9, INFL = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 2e5 + 5;

ll n, m, k = 0;

#include "grader.h"
vll g[maxn];
vll eu;
void dfs(ll u, ll p = -1){
    eu.pb(u);
    for(auto v : g[u]){
        if(v == p) continue;
        dfs(v, u);
    }
}
int findEgg(int _n, vector<pair<int, int>>_ed){
    n = _n;
    for(ll i = 0; i <= n; i ++) g[i].clear();
    for(auto [x, y] : _ed) g[x].pb(y), g[y].pb(x);
    // beautiful = connected
    // onda euler path uzerinde islemek olar
    eu.clear();
    dfs(1);
    // log2(512) > log2(511) ona gore bir denesini default olaraq qoyacam
    ll cv = eu.back(); eu.pop_back();
    ll l = 0, r = len(eu) - 1;
    auto get = [&](ll x) -> bool{
        vector<int> v;
        for(ll i = 0; i <= x; i ++) v.pb(eu[i]);
        return query(v);
    };
    while(l <= r){
        ll md = (l + r) >> 1;
        if(get(md)){
            cv = eu[md];
            r = md - 1;
        }
        else{
            l = md + 1;
        }
    }
    return cv;
}
// void _() {

// }
// signed main() {
//     cin.tie(0)->sync_with_stdio(0);
//     ll t = 1;
//     cin >> t;
//     while(t --) _();
// }

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20