# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1113903 | julia_08 | Easter Eggs (info1cup17_eastereggs) | C++17 | 18 ms | 592 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"
using namespace std;
const int MAXN = 600;
vector<int> adj[MAXN];
int pre[MAXN];
int t = 0;
void dfs(int v, int p){
pre[v] = ++ t;
for(auto u : adj[v]) if(u != p) dfs(u, v);
}
bool ask(int k, int n){
vector<int> islands;
for(int i=1; i<=n; i++){
if(pre[i] <= k){
islands.push_back(i);
}
}
return query(islands);
}
int bs(int n){
int l = 1, r = n;
while(l < r){
int m = l + (r - l) / 2;
if(ask(m, n)) r = m;
else l = m + 1;
}
return r;
}
int findEgg(int n, vector<pair<int, int>> bridges){
t = 0;
for(int i=1; i<=n; i++) adj[i].clear();
for(auto [a, b] : bridges){
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, 1);
int x = bs(n);
for(int i=1; i<=n; i++){
if(pre[i] == x){
return i;
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |