#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int mxN = 525;
vector<int> adj[mxN];
int in[mxN], out[mxN];
int cnt = 0;
void dfs(int u, int p) {
in[u] = ++cnt;
for(auto v : adj[u]) {
if(v == p) continue;
dfs(v, u);
}
out[u] = ++cnt;
return;
}
bool check(int N, int L, int M) {
vector<int> ask;
for(int i = 1; i <= N; ++i) {
if(in[i] >= L && in[i] <= M) {
ask.emplace_back(i);
}
}
return query(ask);
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
// if (query ({1})) return 1;
for(int i = 0; i < N; ++i) {
auto [a,b] = bridges[i];
adj[a].emplace_back(b);
adj[b].emplace_back(a);
}
// euler tour
dfs(1, -1);
int l = 1, r = cnt;
while(l < r) {
int mid = (l+r+1) / 2;
if(check(N, l, mid)) { // check every node that in after l and before mid
l = mid;
} else {
r = mid-1;
}
}
int ans;
for(int i = 1; i <= N; ++i) {
if(in[i] == l) {
ans = i;
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |