#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define sz(x) (int) (x).size()
const int mxN = 520;
vector<int> adj[mxN];
bool vis[mxN];
int cnt;
//int k;
//int res = 0;
/*
bool query(vector<int> &cur){
res++;
for (int c : cur) if (c == k) return 1;
return 0;
}*/
void dfs(int node, int p, vector<int> &cur){
if (sz(cur) >= cnt/2) return;
if (vis[node] == 0){
cur.pb(node);
}
for (int c : adj[node]){
if (c != p) dfs(c,node,cur);
}
}
int findEgg(int n, vector<pair<int,int>> bridges){
for (int i = 0; i < n-1; i++){
adj[bridges[i].f-1].pb(bridges[i].s-1);
adj[bridges[i].s-1].pb(bridges[i].f-1);
}
cnt = n;
memset(vis,0,sizeof(vis));
vector<int> cur;
while (cnt > 1){
dfs(0,-1,cur);
if (query(cur)){
cnt = sz(cur);
memset(vis,1,sizeof(vis));
for (int c : cur) vis[c] = 0;
} else {
cnt -= sz(cur);
for (int c : cur) vis[c] = 1;
}
cur.clear();
}
for (int i = 0; i < n; i++) if (!vis[i]) return i;
}
/*
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n >> k;
k--;
vector<pair<int,int>> b(n-1);
for (int i = 0; i < n-1; i++) cin >> b[i].f >> b[i].s;
cout << findEgg(n,b)+1 << " " << res << '\n';
return 0;
}
*/
Compilation message
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:41:14: warning: control reaches end of non-void function [-Wreturn-type]
41 | vector<int> cur;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
