#include <bits/stdc++.h>
#include "grader.h"
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
const int MAXN = 515;
vector<int> edges[MAXN];
int n;
int sz[MAXN];
bool used[MAXN];
void recalc_size(int u, int p=-1){
sz[u] = 1;
for(auto v : edges[u]){
if(v == p || used[v])continue;
recalc_size(v,u);
sz[u] += sz[v];
}
}
int nn;
int find_centroid(int u, int p=-1){
for(auto v : edges[u]){
if(!used[v] && v != p && sz[v] > nn/2)return find_centroid(v,u);
}return u;
}
vector<int> ttt;
void dfs(int u,int p){
ttt.push_back(u);
for(auto v : edges[u]){
if(v == p || used[v])continue;
dfs(v,u);
}
}
int findEgg(int N, vector<pair<int,int>> bridges){
n = N;
for(auto [u, v] : bridges){
edges[u].push_back(v);
edges[v].push_back(u);
}
int now = 1;
while(true){
recalc_size(now);
nn = sz[now];
int u = find_centroid(now);
now = u;
if(nn == 2){
if(query({now}) == 0){
int x = -1;
for(auto v : edges[now])if(!used[v])x=v;
assert(~x);
now = x;
}break;
}else if(nn == 1){
break;
}
//~ ttt.clear();
//~ dfs(now,now);
//~ for(auto x : ttt){
//~ cout << x << ' ';}cout << '\n';
vector<int> candidates;
for(auto v : edges[u]){
if(!used[v])candidates.push_back(v);
}
srand(time(NULL));
random_shuffle(candidates.begin(), candidates.end());
int sum = 0;
vector<int> f, s;
for(auto v : candidates){
if(sum < nn/2){
sum += sz[v];
f.push_back(v);
}else {
s.push_back(v);
}
}if(!s.size()){
s.push_back(f.back());
f.pop_back();
}
vector<int> toask = {u};
ttt.clear();
for(auto v : f)dfs(v,u);
for(auto v : ttt)toask.push_back(v);
if(query(toask) == 1){
for(auto v : s)used[v] = true;
}else {
for(auto v : f)used[v] = true;
}
}
for(int i=1;i<=n;i++){
edges[i].clear();
}memset(used,0,sizeof used);
return now;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
384 KB |
Number of queries: 5 |
2 |
Partially correct |
2 ms |
384 KB |
Number of queries: 6 |
3 |
Partially correct |
1 ms |
376 KB |
Number of queries: 6 |
4 |
Partially correct |
1 ms |
364 KB |
Number of queries: 5 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
364 KB |
Number of queries: 9 |
2 |
Partially correct |
7 ms |
384 KB |
Number of queries: 14 |
3 |
Partially correct |
16 ms |
376 KB |
Number of queries: 12 |
4 |
Partially correct |
13 ms |
492 KB |
Number of queries: 13 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
16 ms |
364 KB |
Number of queries: 10 |
2 |
Partially correct |
12 ms |
364 KB |
Number of queries: 13 |
3 |
Partially correct |
19 ms |
364 KB |
Number of queries: 13 |
4 |
Partially correct |
13 ms |
364 KB |
Number of queries: 12 |