#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<vector<int>> ve;
vector<int> w;
void dfs(int x, int p){
w.push_back(x);
for (auto el : ve[x]){
if (el != p){
dfs(el, x);
}
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
w.clear();
ve.clear();
ve.resize(N + 1);
for (auto el : bridges){
ve[el.first].push_back(el.second);
ve[el.second].push_back(el.first);
}
dfs(1, -1);
int l = 1, r = N;
while (l <= r){
if (l == r){
return w[l - 1];
}
int mid = (l + r) / 2;
vector<int> rec;
for (int i = 0; i < mid; i++){
rec.push_back(w[i]);
}
bool a = query(rec);
/*if (a && r - l == 0){
return w[l - 1];
}
else if (!a && r -l == 0){
return w[l];
}*/
if (a){
r = mid;
}
else{
l = mid + 1;
}
}
return w[l - 1];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Number of queries: 4 |
2 |
Correct |
1 ms |
344 KB |
Number of queries: 4 |
3 |
Correct |
1 ms |
344 KB |
Number of queries: 4 |
4 |
Correct |
1 ms |
344 KB |
Number of queries: 4 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
976 KB |
Number of queries: 8 |
2 |
Correct |
9 ms |
980 KB |
Number of queries: 9 |
3 |
Correct |
12 ms |
992 KB |
Number of queries: 9 |
4 |
Correct |
11 ms |
1000 KB |
Number of queries: 9 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
1008 KB |
Number of queries: 9 |
2 |
Correct |
11 ms |
1504 KB |
Number of queries: 9 |
3 |
Correct |
13 ms |
984 KB |
Number of queries: 9 |
4 |
Correct |
12 ms |
996 KB |
Number of queries: 9 |