#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;
bool init;
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=sub[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 ;
}
if(sz(stree)==2) {
vector<int> islands;
dfs(stree[0].nd,cnt,islands);
islands.pb(cnt);
F[cnt]=0;
if(query(islands)) {
F[stree[1].nd]=1;
solve(cnt);
}
else {
F[stree[0].nd]=1;
solve(cnt);
}
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[j].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 {
//printf("PROBLEM OCCURED\n");
assert(0);
}
}
int findEgg (int N, vector < pair < int, int > > bridges) {
for(int i=1;i<=N;i++) F[i]=0;
if(!init) {
for(int i=0;i<N-1;i++) {
v[bridges[i].st].pb(bridges[i].nd);
v[bridges[i].nd].pb(bridges[i].st);
// printf("%d %d\n",bridges[i].st,bridges[i].nd);
}
init=true;
}
solve(1);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
400 KB |
Number of queries: 5 |
| 2 |
Incorrect |
3 ms |
440 KB |
Number of queries: 7 |
| 3 |
Incorrect |
4 ms |
440 KB |
Number of queries: 6 |
| 4 |
Incorrect |
4 ms |
440 KB |
Number of queries: 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
440 KB |
Number of queries: 9 |
| 2 |
Incorrect |
24 ms |
576 KB |
Number of queries: 16 |
| 3 |
Incorrect |
24 ms |
676 KB |
Number of queries: 17 |
| 4 |
Runtime error |
7 ms |
828 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
828 KB |
Number of queries: 10 |
| 2 |
Incorrect |
21 ms |
828 KB |
Number of queries: 15 |
| 3 |
Incorrect |
16 ms |
844 KB |
Number of queries: 18 |
| 4 |
Runtime error |
5 ms |
844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
