# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1035458 | TsotneSV | 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>
using namespace std;
/* /\_/\
(= ._.)
/ > \>
*/
#define pb push_back
int findEgg(int N, vector < pair < int, int > > bridges) {
vector<vector<int>> g(N + 1); vector<int> tour;
for(int i=0;i<N-1;i++) {
int u = bridges[i].first,v = bridges[i].second;
g[u].pb(v);
g[v].pb(u);
}
function<void(int,int)> dfs = [&](int v,int p) {
tour.pb(v);
for(int i : g[v]) {
if(i == p) continue;
dfs(i,v);
}
};
dfs(1,0);
int l = 0,r = N-1;
while(l < r) {
int mid = (l + r)/2; vector<int> islands;
for(int i=l;i<=mid;i++) {
islands.pb(tour[i]);
}
if(query(islands)) {
r = mid;
}else {
l = mid + 1;
}
}
return tour[r];
}
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
(= ._.)
/ > \>
*/
#define pb push_back
int findEgg(int N, vector < pair < int, int > > bridges) {
vector<vector<int>> g(N + 1); vector<int> tour;
for(int i=0;i<N-1;i++) {
int u = bridges[i].first,v = bridges[i].second;
g[u].pb(v);
g[v].pb(u);
}
function<void(int,int)> dfs = [&](int v,int p) {
tour.pb(v);
for(int i : g[v]) {
if(i == p) continue;
dfs(i,v);
}
};
dfs(1,0);
int l = 0,r = N-1;
while(l < r) {
int mid = (l + r)/2; vector<int> islands;
for(int i=l;i<=mid;i++) {
islands.pb(tour[i]);
}
if(query(islands)) {
r = mid;
}else {
l = mid + 1;
}
}
return tour[r];
}