Submission #1125571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125571		heavylightdecomp	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	13 ms	512 KiB

eastereggs

#include<bits/stdc++.h>
using namespace std;
#define int signed
#define i32 signed
#define X first
#define Y second
#define pb push_back
using pii = pair<int,int>;
#define vt vector
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define f0r(i,a,b) for(auto i = (a); i != (b); i++)
#define r0f(i,a,b) for(auto i = (a); i >= (b); i--)
#define debug(x) {auto _x=x;cerr<<#x<<": "<<_x<<'\n';};
vt<vt<int>> tr;
vt<int> ord;
int n;
//dfs to get ord array
i32 query(vt<int> islands);
void dfs(int u,int par = -1) {
    ord.pb(u);
    for(int v : tr[u]) if(v != par) {
        dfs(v,u);
    }
}
int findEgg(i32 N, vt<pair<i32,i32>> bridges) {
    n = N;
    tr = vt<vt<int>> (N+1);
    for(auto [u,v] : bridges) {
        tr[u].pb(v);
        tr[v].pb(u);
    }
    ord.clear();
    dfs(1);
    int lo = 1, hi = N;
    while(lo < hi) {
        int mid = (lo+hi)/2;
        vt<int> eggs;
        f0r(i,0,mid) {
            eggs.pb(ord[i]);
        }
        if(query(eggs)) {
            hi = mid;
        } else {
            lo = mid+1;
        }
    }
    //narrowed it down to 1? no need to check anymore.
    return ord[lo-1];

}

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