# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
243037 | soyeon_ss | Easter Eggs (info1cup17_eastereggs) | C++14 | 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>
#define int long long
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define for1(i, a, b) for(i = a; i <= b; ++i)
#define for0(i, a, b) for(i = a; i < b; ++i)
#define forw1(i, a, b) for(i = a; i >= b; --i)
#define forw0(i, a, b) for(i = a - 1; i >= b; --i)
#define fora(v, a) for(auto v : a)
#define bp __builtin_popcount
#define bpll __builtin_popcountll
using namespace std;
using cd = complex<double>;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<cd> vcd;
typedef vector<ii> vii;
typedef vector<vector<int> > vvi;
const int modd1 = 1e9 + 7, modd2 = 998244353, maxn = 520, K = 26, inf = 1e9, infll = 1e18;
const double pi = acos(-1);
int n, m, used[maxn];
vi gr[maxn], tp;
int dfs(int st){
used[st] = 1;
tp.pb(st);
int i, j, k, l, r;
for0(i, 0, (int)gr[st].size()){
if(!used[gr[st][i]]){
dfs(gr[st][i]);
}
}
}
int binsearch(int lo, int hi){
if(lo == hi){
return lo;
}
int mid = (lo + hi) >> 1;
int i; vi kk;
for1(i, 0, mid){
kk.pb(tp[i]);
}
if(query(kk)){
return binsearch(lo, mid);
}
else{
return binsearch(mid + 1, hi);
}
}
int findEgg(int N, vii bridges){
int i;
for0(i, 1, N){
gr[bridges[i - 1].fi].pb(bridges[i - 1].se);
gr[bridges[i - 1].se].pb(bridges[i - 1].fi);
}
dfs(1);
return tp[binsearch(0, n - 1)];
}