| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 98326 | 2019-02-22T12:04:46 Z | tmk | Easter Eggs (info1cup17_eastereggs) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h>
using namespace std;
#ifndef d
#define d(...)
#endif
#define st first
#define nd second
#define pb push_back
#define siz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
typedef long long LL;
typedef long double LD;
constexpr int INF=1e9+7;
constexpr LL INFL=1e18;
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
return os << "(" << P.st << "," << P.nd << ")";
}
constexpr int maxn = 520;
int n;
vector<int> G[maxn];
bool vis[maxn];
vector<int> get_bfs_order() {
vector<int> ret;
ret.push_back(1);
vis[1] = true;
for(int i=0; i<siz(ret); i++) {
auto w = ret[i];
for(auto v:G[w])
if(not vis[v]) {
vis[v] = true;
ret.push_back(v);
}
}
return ret;
}
int findEgg(int _n, vector<pair<int, int>> edges) {
n = _n;
for(int i=1; i<=n; i++)
G[i].clear(), vis[i] = false;
for(auto& e:edges) {
G[e.st].push_back(e.nd);
G[e.nd].push_back(e.st);
}
auto&& v = get_bfs_order();
int l = 0, r = n-1;
while(l < r) {
auto s = (l+r) / 2;
if(query(vector<int>(v.begin(), v.begin() + s)))
r = s;
else
l = s;
}
return v[l];
}