#include "park.h"
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
const int maxn = 1500+5;
#ifdef BALBIT
vector<int> gra[maxn];
bool seen[maxn];
bool dfs(int v, int b, int Place[]) {
if (v == b) return 1;
seen[v] = 1;
for (int u : gra[v]) {
if (!seen[u] && Place[u]) {
if (dfs(u,b,Place)) return 1;
}
}
return 0;
}
bool Ask(int a, int b, int Place[]) {
assert(Place[a] && Place[b]);
memset(seen, 0, sizeof seen);
return dfs(a,b,Place);
}
void Answer(int a, int b) {
bug("answering ", a,b);
}
#endif // BALBIT
namespace {
vector<int> tree[maxn];
bool intree[maxn];
int n;
}
static int Place[1400];
bool ask(int a,int b,vector<int> v) {
if (a==b) return 1;
memset(Place, 0, sizeof Place);
for (int x : v) Place[x] = 1;
return Ask(a,b,Place);
}
void addtree (int a, int b) {
bug("edge ", a,b);
Answer(a,b);
tree[a].pb(b); tree[b].pb(a);
intree[a] = intree[b] = 1;
}
void build(int a, int b) {
assert(a!=b);
if (ask(a,b,{a,b})) {
addtree(a,b); return;
}
vector<int> can; // candidates
REP(i,n) {
if (i!=a && i!=b && !intree[i]) {
can.pb(i);
}
}
int l = 0, r = SZ(can); // the graph should be connected, so it'll find something?????
while (l!=r) {
int mid = (l+r)/2;
vector<int> go(can.begin(), can.begin() + mid);
go.pb(a); go.pb(b);
if (ask(a,b,go)) {
// maybe i can go lower
r = mid;
}else{
l = mid+1;
}
}
assert(l!=0); // otherwise they'd be connected!?
int ele = can[l-1];
build(a,ele);
build(ele,b);
}
void dfs(int v, int p, vector<int> &tnodes) {
tnodes.pb(v);
for (int u : tree[v]) {
if( u != p) {
dfs(u, v, tnodes);
}
}
}
void buildtree(){
intree[0] = 1;
for (int i = 1; i<n; ++i) {
if (!intree[i]) {
// find a person in the current tree to branch off of
vector<int> tnodes; // ok tnodes should be sorted by dfs order or depth... sorry
dfs(0, -1, tnodes);
vector<int> nottnodes;
REP(j,n) if (!intree[j]) nottnodes.pb(j);
int l = 1, r = SZ(tnodes);
while (l!=r) {
int mid = (l+r)/2;
vector<int> go (tnodes.begin(), tnodes.begin() + mid);
go.insert(go.end(), nottnodes.begin(), nottnodes.end());
if (ask(0, i, go)) {
// reachable... i can use fewer nodes
r = mid;
}else {
l = mid+1;
}
}
int a = tnodes[l-1];
bug(a, i);
build(a,i);
}
}
}
void Detect(int T, int N) {
n=N;
buildtree();
}
#ifdef BALBIT
signed main(){
IOS();
vector<pii> edges = {{0,4}, {0,2}, {1,2}, {1,3}};
REP(i, SZ(edges)) {
gra[edges[i].f].pb(edges[i].s);
gra[edges[i].s].pb(edges[i].f);
}
int N = SZ(edges)+1;
Detect(-1, N);
}
#endif
Compilation message
park.cpp: In function 'bool ask(long long int, long long int, std::vector<long long int>)':
park.cpp:80:20: error: cannot convert 'long long int*' to 'int*'
80 | return Ask(a,b,Place);
| ^~~~~
| |
| long long int*
In file included from park.cpp:1:
park.h:1:29: note: initializing argument 3 of 'int Ask(int, int, int*)'
1 | int Ask(int A , int B , int Place[]);
| ~~~~^~~~~~~
