#include <bits/stdc++.h>
#include "grader.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define pii pair<int, int>
using namespace std;
const int NN = 513;
vector<pii> edges[NN];
vector<int> vv[NN];
int nn, used[NN];
bool ok;
void dfs(int u, int p = -1){
//if(ok) cout<<u<<" ";
vv[u].pb(u);
for(auto x:edges[u]){
if(x.ff == p || used[x.ss]) continue;
dfs(x.ff, u);
for(auto xx:vv[x.ff]) vv[u].pb(xx);
}
}
/*
13
1 2
1 5
1 6
2 3
2 4
1 7
7 8
7 9
8 10
8 11
9 12
9 13
13
1 2 3 4 5 6 7 8 9 10 11 12 13
16
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
8
1 2
1 3
1 4
1 5
1 6
1 7
1 8
8
1 2 3 4 5 6 7 8
*/
int dfs_cc(int u, int p = -1){
pii mx = {-1, -1};
for(auto x:edges[u]){
if(used[x.ss] || x.ff == p) continue;
if(sz(vv[x.ff]) > mx.ff) mx.ff = sz(vv[x.ff]), mx.ss = x.ff;
}
if(mx.ff * 2 >= nn) return dfs_cc(mx.ss, u);
return u;
}
int solve(int cur){
if(nn == 1) return cur;
for(int i=0;i<NN;i++) vv[i].clear();
dfs(cur);
//cout<<"\n";
//cout<<nn<<" "<<cur<<"\n";
if(nn == 1) return 0;
int centr = dfs_cc(cur);
for(int i=0;i<NN;i++) vv[i].clear();
dfs(centr);
vector<pair<int, pii>> childs;
vector<int> a;
for(auto x:edges[centr]) { a.pb(sz(vv[x.ff])); childs.pb({sz(vv[x.ff]), x}); }
//sort(childs.begin(), childs.end());
vector<int> qq, start;
qq.pb(centr);
vector<int> uu(NN, 0);
//int last = -1, nw = -1, i;
int gg = (nn+1)/2;
vector<int> dp(NN, 0), par(NN, 0);
dp[1] = 1, par[1] = -1;
for(int i=0;i<sz(a);i++){
for(int j=gg;j>a[i];j--){
if(dp[j]) continue;
if(dp[j - a[i]]){
dp[j] = 1;
par[j] = i;
}
}
}
//for(auto x:a) cout<<x<<" ";
//cout<<"\n";
//for(int i=0;i<=gg;i++) cout<<dp[i]<<" ";
//cout<<"\n";
vector<int> uch(NN);
for(int i=gg;i>=0;i--){
if(dp[i]){
int tt = i;
while(par[tt] != -1){
//int last = tt;
auto x = childs[par[tt]];
for(auto xx : vv[x.ss.ff]) qq.pb(xx);
uu[x.ss.ss] = 1;
uch[par[tt]] = 1;
//tt = par[tt];
tt -= a[par[tt]];
}break;
}
}
for(int i=0;i<sz(childs);i++){
if(uch[i]) continue;
auto x = childs[i];
for(auto xx : vv[x.ss.ff]) start.pb(xx);
}
for(auto &x:qq) x += 1;
//for(auto x:qq) cout<<x<<" ";
//cout<<"\n";
//for(auto x:start) cout<<x+1<<" ";
//cout<<"\n";
//cout<<"\n___________\n";
int res = query(qq);
if(res){
for(auto x:edges[centr]) if(!uu[x.ss]) used[x.ss] = 1;
nn = sz(qq);
if(nn == 2){
if(query({qq.back()})) return qq.back()-1;
else { qq.pop_back(); return qq.back()-1; }
}
if(nn == 1) return centr;
return solve(centr);
}
else{
for(auto x:edges[centr]) if(uu[x.ss]) used[x.ss] = 1;
nn = (nn - sz(qq));
if(sz(start) == 1) return start.back();
if(sz(start) == 2){
if(query({start.back()+1})) return start.back();
else { start.pop_back(); return start.back(); }
}
nn++;
return solve(centr);
}
}
int findEgg (int N, vector < pair < int, int > > bridges){
memset(used, 0, sizeof used);
for(int i=0;i<NN;i++) edges[i].clear(), vv[i].clear();
nn = N;
for(int i=0;i<sz(bridges);i++){
edges[bridges[i].ff-1].pb({bridges[i].ss-1, i});
edges[bridges[i].ss-1].pb({bridges[i].ff-1, i});
}
int res = solve(0)+1;
//cout<<res<<"\n___________\n";
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
2 ms |
364 KB |
Number of queries: 5 |
| 2 |
Partially correct |
2 ms |
412 KB |
Number of queries: 5 |
| 3 |
Partially correct |
2 ms |
364 KB |
Number of queries: 5 |
| 4 |
Partially correct |
1 ms |
364 KB |
Number of queries: 5 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
620 KB |
Number of queries: 9 |
| 2 |
Partially correct |
11 ms |
492 KB |
Number of queries: 10 |
| 3 |
Partially correct |
22 ms |
528 KB |
Number of queries: 10 |
| 4 |
Partially correct |
21 ms |
492 KB |
Number of queries: 10 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
85 ms |
1132 KB |
Number of queries: 10 |
| 2 |
Partially correct |
17 ms |
492 KB |
Number of queries: 10 |
| 3 |
Partially correct |
22 ms |
492 KB |
Number of queries: 10 |
| 4 |
Partially correct |
26 ms |
620 KB |
Number of queries: 10 |
