Submission #549991

#	Time	Username	Problem	Language	Result	Execution time	Memory
549991		balbit	Park (JOI17_park)	C++14	Compilation error	0 ms	0 KiB

park

#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 (stderr)

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[]);
      |                         ~~~~^~~~~~~