#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int MAXN = 520;
set<int> g[MAXN];
int n, sub[MAXN];
vector<int> cenTree[MAXN], what[MAXN];
int dfs(int u,int p){
sub[u] = 1;
for(auto v:g[u]) if(v != p){
sub[u] += dfs(v, u);
}
return sub[u];
}
int centroid(int u, int p, int mx){
for(auto v:g[u]) if(v != p){
if(sub[v] > (mx / 2)) return centroid(v, u, mx);
}
return u;
}
void make(int u, int p){
int mx = dfs(u, p);
int c = centroid(u, p, mx);
if(p == 0) p = c;
else{
cenTree[p].push_back(c);
cenTree[c].push_back(p);
}
vector<int> temp(g[c].begin(), g[c].end());
for(auto v:temp){
g[c].erase(v);
g[v].erase(c);
make(v, c);
}
}
void dfs2(int u,int p){
what[u].push_back(u);
for(auto v:cenTree[u]) if(v != p){
dfs2(v, u);
for(auto x:what[v]) what[u].push_back(x);
}
}
int get(int u,int p){
for(auto v:cenTree[u]) if(v != p){
vector<int> lol;
for(auto w:cenTree[v]){
if(w == u) continue;
for(auto k:what[w]) lol.push_back(k);
}
lol.push_back(v);
// cout << v << " -> ";
// for(auto k:lol) cout << k << " ";
// cout << endl;
int q = query(lol);
if(q == 1){
// cout << v << endl;
return get(v, u);
}
}
return u;
}
int findEgg (int N, vector < pair < int, int > > bridges){
/*
set<int> g[MAXN];
int n, sub[MAXN];
vector<int> cenTree[MAXN], what[MAXN];
*/
for(int i = 0;i <MAXN;i++){
sub[i] = 0;
cenTree[i].clear();
what[i].clear();
g[i].clear();
}
n = N;
for(int i = 0;i < N-1;i++){
int u = bridges[i].first;
int v = bridges[i].second;
g[u].insert(v);
g[v].insert(u);
}
make(1, 0);
dfs2(1, 0);
return get(1, 0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
328 KB |
Number of queries: 6 |
2 |
Partially correct |
1 ms |
328 KB |
Number of queries: 6 |
3 |
Partially correct |
1 ms |
328 KB |
Number of queries: 10 |
4 |
Partially correct |
2 ms |
328 KB |
Number of queries: 15 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
584 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
704 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |