#include <bits/stdc++.h>
#include "grader.h"
#define mp make_pair
#define F first
#define S second
#define eb emplace_back
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
using pii = pair<int, int>;
int n;
vector<vector<int>> g;
vector<int> tmp;
void dfs1(int now, int p){
tmp.eb(now);
for(int i : g[now]){
if(i == p) continue;
dfs1(i, now);
}
}
vector<int> qs;
set<int> ts;
bool dfsq(int now, int p){
bool tmp = ts.find(now) != ts.end();
//cerr << "dfsq " << now << " " << tmp << "\n";
for(int i : g[now]){
if(i == p) continue;
tmp = dfsq(i, now) || tmp;
}
if(tmp) qs.eb(now);
return tmp;
}
int qry(vector<int>& _s){
qs.clear();
ts.clear();
for(int i : _s) ts.insert(i);
dfsq(1, 1);
//cerr << "real ";
//printv(qs, cerr);
//printv(ts, cerr);
return query(qs);
}
int qry(int l, int r){
vector<int> s;
for(int i = l; i <= r; i++) s.eb(tmp[i]);
//cerr << "qry " << l << " " << r << " ";
//printv(s, cerr);
return qry(s);
}
int findEgg (int N, vector<pii> bridges){
//cerr << "find " << N << "\n";
g.clear();
tmp.clear();
n = N;
g.resize(n + 1);
for(int i = 0; i < n - 1; i++){
int u, v;
tie(u, v) = bridges[i];
g[u].eb(v);
g[v].eb(u);
}
dfs1(1, 1);
//printv(tmp, cerr);
int l = 0, r = n - 1;
while(l < r){
int m = (l + r) / 2;
if(!qry(l, m)) l = m + 1;
else r = m;
}
return tmp[l];
}
Compilation message
permutation.cpp:2:10: fatal error: grader.h: No such file or directory
2 | #include "grader.h"
| ^~~~~~~~~~
compilation terminated.
