| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1314937 | jfioashfn333 | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include "grader.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <set>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define pp pop_back
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define r0 return 0
using namespace std;
const int N = 5 * 1e5 + 5, M = 55, MOD = 998244353;
int x,y,xx,yy,n,m,k,l,ans,tm;
vector <int> g[N],rd;
int fix[N],tc[N];
void dfs (int x,int tm) {
fix[x] = tm + 1;
tm = tm + 1;
tc[x] = 1;
for (auto to : g[x]) {
if (tc[to] == 1) continue;
rd.pb(to);
dfs(to,tm);
}
}
int check (int mid) {
vector <int> h;
for (int i = 1; i <= mid; i++) {
h.pb(fix[i]);
}
tm = 0;
return query(h);
}
int findEgg(int N, vector <pii> bridges){
for (int i = 1; i <= n; i++) {
g[i].clear();
fix[i] = 0;
}
n = N;
for (pii to : bridges) {
g[to.ff].pb(to.ss);
g[to.ss].pb(to.ff);
}
dfs(1,1);
int l = 1,r = n - 1, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (ans == -1) {
return fix[n];
} else {
return fix[ans];
}
return ans;
}