#include <bits/stdc++.h>
#include "grader.h"
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mid ((x + y) / 2)
#define left (ind * 2)
#define right (ind * 2 + 1)
#define mp make_pair
#define timer ((double)clock() / CLOCKS_PER_SEC)
#define endl "\n"
#define spc " "
#define d1(x) cerr<<#x<<":"<<x<<endl
#define d2(x, y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define d3(x, y, z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long int lli;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<double, double> dd;
const int N = (int)(1e6 + 5);
const int LOG = (int)(20);
int n, mark[N];
vector<int> v[N], ar;
queue<int> q;
void bfs() {
q.push(1);
while(!q.empty()) {
int x = q.front();
q.pop();
if(mark[x])
continue;
ar.pb(x);
mark[x] = 1;
for(auto i : v[x])
if(!mark[i])
q.push(i);
}
}
bool check(int x) {
vector<int> vec;
for(int i = 0; i < x; i++)
vec.pb(ar[i]);
return query(vec);
}
int bs(int x, int y) {
if(x == y)
return x;
if(x + 1 == y) {
if(check(x))
return x;
return y;
}
if(check(mid))
return bs(x, mid);
else
return bs(mid + 1, y);
}
int findEgg (int _N, vector < pair < int, int > > bridges)
{
n = _N;
for(auto i : bridges) {
v[i.fi].pb(i.se);
v[i.se].pb(i.fi);
}
bfs();
return bs(1, n);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
48120 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
48120 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
48216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
