# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
892745 | Isam | Easter Eggs (info1cup17_eastereggs) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "grader.h"
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(37)
#endif
using namespace std;
constexpr int sz = 2e5 + 5;
#define pii pair<int, int>
#define F first
#define S second
int timel;
int tin[sz];
vector<vector<int>> g;
inline void Dfs(int node, int fa = 1){
tin[++timel] = node;
for(auto &to : g[node]){
if(to == fa) continue;
Dfs(to, node);
}
return;
}
bool Query(int l, int r){
vector<int> v;
for(register int i{l}; i <= r; ++i) v.emplace_back(tin[i]);
return query(v);
}
int findEgg(int N, vector < pair < int, int > > bridges){
g.resize(N+1);
for(register int i(0), a, b; i < N; ++i){
a = bridges[i].F, b = bridges[i].S;
g[a].emplace_back(b), g[b].emplace_back(a);
}
Dfs(1)
int l = 1, r = N, mid, best;
while(l < r){
mid = l + ((r - l) >> 1);
if(Query(l, mid)){
r = mid;
}else{
l = mid + 1;
}
}
return tin[r];
}