#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;
bool dp[MAX];
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 do_dp(vector<ii> now) {
for(int i=0;i<=glosub;i++) {
dp[i]=0;
}
dp[0]=1;
for(int i=0;i<sz(now);i++) {
for(int j=glosub-now[i].st;j>=0;j--) {
dp[j+now[i].st]|=dp[j];
}
}
//cerr<<"OK\n";
//cerr<<glosub<<"\n";
// for(int i=0;i<=glosub;i++) cerr<<dp[i]<<" ";
// cerr<<endl;
}
vector<int> find_them(vector<ii> now,int value,int cnt) {
vector<int> res;
int last=0;
for(int i=value;i>0;) {
for(;last<sz(now);last++) {
if(i>=now[last].st && dp[i-now[last].st]) {
i-=now[last].st;
dfs(now[last].nd,cnt,res);
last++;
break ;
}
}
}
//cerr<<"OK\n";
return res;
}
void solve(int node) {
fsubs(node,0);
glosub=sub[node];
int cnt=fcnt(node,0);
fsubs(cnt,0);
vector<ii> stree;
//cerr<<"Cnt is "<<cnt<<endl;
for(int i:v[cnt]) {
if(F[i]) continue ;
stree.pb({sub[i],i});
}
sort(all(stree));
if(sz(stree)==1) {
vector<int> is;
is.pb(cnt);
if(query(is)) {
ans=cnt;
}
else ans=stree[0].nd;
return ;
}
do_dp(stree);
for(int i=glosub/2;i>0;i--) {
if(dp[i]) {
vector<int> subs=find_them(stree,i,cnt);
subs.pb(cnt);
//cerr<<"TO GO\n";
//for(auto go:subs) cerr<<go<<' ';
//cerr<<endl;
if(query(subs)) {
for(int go:v[cnt]) {
if(F[go]) continue ;
F[go]=1;
}
for(int go:subs) {
F[go]=0;
}
}
else {
for(int go:subs) {
F[go]=1;
}
}
solve(cnt);
return ;
}
}
ans=cnt;
}
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);
}
init=true;
}
solve(1);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1087 ms |
248 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1080 ms |
312 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1079 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
