#include <vector>
#include <cassert>
#include "grader.h"
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
const int mx = 512;
vi edge[1+mx];
vi ord(1, 0);
vi vis(1+mx, 0);
void dfs(int u, int p)
{
vis[u] = 1;
ord.push_back(u);
for(int v : edge[u])
{
if(!vis[v])
dfs(v, u);
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
for(pii b: bridges)
{
edge[b.first].push_back(b.second);
edge[b.second].push_back(b.first);
}
dfs(1, 1);
assert(int(bridges.size()) == N-1);
// assert(int(ord.size()) == N);
int lo = 1, hi = N;
while(lo != hi)
{
int mid = (lo+hi)/2;
vi qr;
for(int i = 1; i <= mid; i++)
qr.push_back(ord[i]);
if(query(qr))
hi = mid;
else
lo = mid+1;
}
return ord[lo];
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Number of queries: 4 |
2 |
Correct |
1 ms |
200 KB |
Number of queries: 4 |
3 |
Correct |
1 ms |
200 KB |
Number of queries: 4 |
4 |
Correct |
1 ms |
200 KB |
Number of queries: 4 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
328 KB |
Number of queries: 8 |
2 |
Correct |
16 ms |
408 KB |
Number of queries: 9 |
3 |
Correct |
14 ms |
488 KB |
Number of queries: 9 |
4 |
Correct |
16 ms |
604 KB |
Number of queries: 9 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
628 KB |
Number of queries: 9 |
2 |
Correct |
15 ms |
636 KB |
Number of queries: 9 |
3 |
Correct |
16 ms |
612 KB |
Number of queries: 9 |
4 |
Correct |
19 ms |
476 KB |
Number of queries: 9 |