#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg(int N, vector<pair<int,int>> bridges){
vector<int> adj[N];
vector<int> tin(N),seq(N);
int t = 0;
function<void(int,int)> dfs = [&](int v,int par){
seq[t] = v;
tin[v] = t++;
for(auto u:adj[v]){
if(u != par)
dfs(u,v);
}
};
for(int i = 0;i<N-1;++i){
bridges[i].first--,bridges[i].second--;
adj[bridges[i].first].push_back(bridges[i].second);
adj[bridges[i].second].push_back(bridges[i].first);
}
dfs(0,-1);
int l = 0,r = N-1;
while(l < r){
int m = (l + r)/2;
vector<int> v;
for(int i = 0;i<=m;i++){
v.push_back(seq[i] + 1);
}
if(query(v)){
r = m;
}
else l = m + 1;
}
return seq[l] + 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Number of queries: 4 |
2 |
Correct |
1 ms |
208 KB |
Number of queries: 4 |
3 |
Correct |
1 ms |
208 KB |
Number of queries: 4 |
4 |
Correct |
1 ms |
208 KB |
Number of queries: 4 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
336 KB |
Number of queries: 8 |
2 |
Correct |
12 ms |
336 KB |
Number of queries: 9 |
3 |
Correct |
21 ms |
344 KB |
Number of queries: 9 |
4 |
Correct |
20 ms |
348 KB |
Number of queries: 9 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
380 KB |
Number of queries: 9 |
2 |
Correct |
17 ms |
336 KB |
Number of queries: 9 |
3 |
Correct |
18 ms |
356 KB |
Number of queries: 9 |
4 |
Correct |
16 ms |
360 KB |
Number of queries: 9 |