#include<bits/stdc++.h>
#include "grader.h"
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000000000000000
#define MOD 1000000007
#define MAX 555
#define LOG 22
using namespace std;
int glosub,ans;
int sub[MAX],F[MAX];
vector<int> v[MAX];
void dfs(int node,int ata,vector<int>& islands) {
islands.pb(node);
for(int i:v[node]) {
if(i==ata || F[i]) continue ;
dfs(i,node,islands);
}
}
int fcnt(int node,int ata) {
for(int i:v[node]) {
if(i==ata || F[i]) continue ;
if(sub[i]>=glosub/2) return fcnt(i,node);
}
return node;
}
void fsubs(int node,int ata) {
sub[node]=1;
for(int i:v[node]) {
if(i==ata || F[i]) continue ;
fsubs(i,node);
sub[node]+=sub[i];
}
}
void solve(int node) {
//printf("Curnode-->%d\n",node);
fsubs(node,0);
glosub=node;
int cnt=fcnt(node,0);
//printf("Cnt found-->%d\n",cnt);
fsubs(cnt,0);
F[cnt]=1;
vector<ii> stree;
for(int i:v[cnt]) {
if(F[i]) continue ;
stree.pb({sub[i],i});
}
sort(all(stree),greater<ii>());
// for(ii i:stree) printf("node-->%d size-->%d\n",i.nd,i.st);
if(sz(stree)==1) {
vector<int> islands;
islands.pb(cnt);
int res=query(islands);
if(res) {
ans=cnt;
}
else {
ans=stree[0].nd;
}
return ;
}
ii odd={-1,-1};
if(sz(stree)&1) {
odd=stree.back();
stree.ppb();
}
for(int i=0;i+1<sz(stree);i+=2) {
vector<int> islands;
dfs(stree[i].nd,cnt,islands);
dfs(stree[i+1].nd,cnt,islands);
islands.pb(cnt);
int res=query(islands);
if(res) {
F[cnt]=0;
for(int j=0;j<sz(stree);j++) {
if(i!=j && i+1!=j) F[stree[i].nd]=1;
}
if(odd.nd!=-1) F[odd.nd]=1;
solve(cnt);
return ;
}
}
if(odd.st!=-1) {
F[cnt]=0;
for(int i=0;i<sz(stree);i++) F[stree[i].nd]=1;
solve(cnt);
return ;
}
else assert(0);
}
int findEgg (int N, vector < pair < int, int > > bridges) {
for(int i=1;i<=N;i++) v[i].clear();
for(int i=1;i<=N;i++) F[i]=0;
for(int i=0;i<N-1;i++) {
v[bridges[i].st].pb(bridges[i].nd);
v[bridges[i].nd].pb(bridges[i].st);
}
solve(1);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
448 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
648 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
