Submission #1211077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211077		ziewacz	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	117 ms	196608 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define imie(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const int mod=1e9+7;
const int n=513;
vector<int> graf[n];
vector<int> ord;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

void dfs(int v, int par) {
    ord.push_back(v);
    for(auto &u : graf[v]) {
        if(v != par) {
            dfs(u, v);
        }
    }
}

int findEgg(int N, vector<pair<int, int>> bridges) {
    for(auto &p : bridges) {
        graf[p.first].push_back(p.second);
        graf[p.second].push_back(p.first);
    }
    dfs(1, -1);
    int l = 0, r = N;
    int mid = (l + r) >> 1;
    vector<int> v;
    while(l < r) {
        for(int i = 0; i <= mid; i++) {
            v.push_back(ord[i]);
        }
        if(!query(v)) {
            l = mid + 1;   
        } else {
            r = mid;
        }
    }
    return v[l];
}

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