#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left isc+isc
#define right isc+isc+1
#define mid (l+r)/2
#define FAfi_IO ios_base::sync_with_fidio(false);
#define escl '\n'
typedef long long int ll;
const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int maxN = 515;
const int M = 1e4 + 5;
const int SQ = 350;
const int MOD = 998244353;
typedef long long int lli;
typedef pair<int,int> pii;
vector <int> ed[maxN],ask;
int n,pos[maxN],mark[maxN],kal;
bool ilk = true;
void find(int cur,int back) {
if (kal == 0) return;
if (pos[cur] != -1) {
mark[cur] = 1;
kal--;
ask.pb(cur);
}
for (auto i : ed[cur]) {
if (i != back) find(i,cur);
}
}
int solve(int sz) {
if (sz == 1) {
for (int i = 1 ; i <= n ; i++)
if (pos[i] != -1) return i;
}
kal = sz / 2;
memset(mark,0,sizeof mark);
find(1,-1);
// for (auto i : ask)
// printf("%d ",i);
// puts("");
if (query(ask)) {
while(len(ask)) {
if (mark[ask.back()] == 1) ask.pop_back();
else break;
}
// d1("yes");
for (int i = 1 ; i <= n ; i++) if (mark[i] == 0) pos[i] = -1;
return solve(sz / 2);
}
else {
// d1("no");
for (int i = 1 ; i <= n ; i++) if (mark[i] == 1) pos[i] = -1;
return solve(sz - sz / 2);
}
}
int findEgg (int N, vector < pair < int, int > > bridges) {
ask.clear();
memset(pos,0,sizeof pos);
memset(mark,0,sizeof mark);
if (ilk) {
for (auto i : bridges) {
ed[i.fi].pb(i.sc);
ed[i.sc].pb(i.fi);
}
ilk = false;
}
n = N;
return solve(n);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
376 KB |
Number of queries: 4 |
2 |
Correct |
2 ms |
440 KB |
Number of queries: 4 |
3 |
Correct |
4 ms |
440 KB |
Number of queries: 4 |
4 |
Correct |
3 ms |
444 KB |
Number of queries: 4 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
512 KB |
Number of queries: 8 |
2 |
Correct |
22 ms |
512 KB |
Number of queries: 9 |
3 |
Correct |
26 ms |
516 KB |
Number of queries: 9 |
4 |
Correct |
32 ms |
572 KB |
Number of queries: 9 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
624 KB |
Number of queries: 9 |
2 |
Correct |
29 ms |
624 KB |
Number of queries: 9 |
3 |
Correct |
30 ms |
624 KB |
Number of queries: 9 |
4 |
Correct |
38 ms |
624 KB |
Number of queries: 9 |