#include <bits/stdc++.h>
#include "grader.h"
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
/*int query(vector < int > islands){
cout << "-> ";
for(auto u : islands)
cout << u << ' ';
cout << '\n';
return rand()%2;
}*/
vector<int> g[600];
int ok[600];
int sz[600];
void calcsz(int v, int prt){
sz[v] = 1;
for(auto u : g[v]){
if(u == prt || ok[u] == 0) continue;
calcsz(u, v);
sz[v] += sz[u];
}
}
vector<int> curv, othv;
void get(int v, int prt, vector<int> &curv){
curv.pb(v);
for(auto u : g[v]){
if(u == prt || ok[u] == 0) continue;
get(u, v, curv);
}
}
vector<bitset<600>> bs[600];
vector<pii> child[600];
pii curvert;
void dfs1(int v, int prt){
child[v].clear();
child[v].pb({-1, -1});
for(auto u : g[v])
if(ok[u])
child[v].pb({sz[u], u});
bs[v].clear();
bs[v].resize(child[v].size());
bs[v][0][0] = 1;
for(int i = 1; i < child[v].size(); ++i)
bs[v][i] = (bs[v][i-1]|(bs[v][i-1]<<child[v][i].ff));
for(int i = (sz[v]-1)/2; i >= 0; --i)
if(bs[v][child[v].size()-1][i]){
curvert = max(curvert, {i, v});
//cout << i << ' ' << v << '\n';
break;
}
for(auto u : g[v]){
if(u == prt || ok[u] == 0) continue;
int bef = sz[u];
sz[u] = sz[v];
sz[v] -= bef;
dfs1(u, v);
sz[v] += bef;
sz[u] = bef;
}
}
void dfs2(int v){
int cur = curvert.ff;
curv.clear(); othv.clear();
curv.pb(v);
othv.pb(v);
for(int i = child[v].size()-1; i >= 1; --i){
if(cur-child[v][i].ff >= 0 && bs[v][i-1][cur-child[v][i].ff]){
get(child[v][i].ss, v, curv);
cur -= child[v][i].ff;
}
else
get(child[v][i].ss, v, othv);
}
//cout << curv.size() << ' ' << othv.size() << '\n';
if(query(curv) == 0)
swap(curv, othv);
}
int findEgg(int N, vector<pair<int, int>> bridges){
for(auto u : bridges){
g[u.ff].pb(u.ss);
g[u.ss].pb(u.ff);
}
for(int i = 1; i <= N; ++i)
curv.pb(i);
while(1){
curvert = {0, 0};
int befsize = curv.size();
if(curv.size() == 1) return curv[0];
for(int i = 1; i <= N; ++i)
ok[i] = 0;
for(auto u : curv)
ok[u] = 1;
int root = curv[0];
calcsz(root, 0);
dfs1(root, 0);
dfs2(curvert.ss);
//assert(curv.size() < befsize);
}
}
/*int main(){
srand(time(NULL));
cout << findEgg(4, {{1, 2}, {2, 3}, {3, 4}}) << '\n';
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
}*/
Compilation message
eastereggs.cpp: In function 'void dfs1(int, int)':
eastereggs.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i = 1; i < child[v].size(); ++i)
| ~~^~~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:99:13: warning: unused variable 'befsize' [-Wunused-variable]
99 | int befsize = curv.size();
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
29 ms |
760 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 |
2 ms |
896 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 |
Execution timed out |
3066 ms |
640 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
