Submission #550026

#	Time	Username	Problem	Language	Result	Execution time	Memory
550026		balbit	Park (JOI17_park)	C++14	100 / 100	241 ms	2128 KiB

park

#ifndef BALBIT
#include "park.h"
#endif
#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 deg[maxn]; // additional degree
    int n;
    int from[maxn];
    set<pii> done;
}
static int Place[1400];

bool ask(int a,int b,vector<int> v) {
    if (a==b) return 1;
    if (a > b) swap(a,b);
    memset(Place, 0, sizeof Place);
    for (int x : v) Place[x] = 1;
    assert(Place[a] && Place[b]);
    return Ask(a,b,Place);
}

void answer(int a, int b) {
    if (a > b) swap(a,b);
    if (done.count({a,b})) return;
    done.insert({a,b});
    Answer(a,b);
    ++deg[a]; ++deg[b];
}

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) {
    from[v] = p;
    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 findculprit(int v, int u, int uno) {
    // find stuff on the other side of u
    // u cannot take stuff in the subtree of uno
    bug(v,u,uno);
    for (int x : tree[u]) {
        if (x != uno) {
            if (deg[v] >= 7) break;
            // is there some sneaker in this subtree????
            vector<int> gt;
            dfs(x,u,gt);
            bug(SZ(gt));
            int L = 0;
            vector<int> nope(n); // nope[i] = 1 if i was erased by one of the subtrees
            while (deg[v] < 7 && L < SZ(gt)) {
                vector<int> go;
                REP(j, SZ(gt)) {
                    if (!nope[gt[j]]) go.pb(gt[j]);
                }
                go.pb(v);
                if (!ask(v,x,go)) break;
                bug("yoooo");
                // dammit! there is an edge pointing in here!
                // find the edge pointing in here with the smallest dfs index
                int l = L, r = SZ(gt)-1;
                while (l!=r) {
                    int mid = (l+r)/2;
                    go.clear();
                    REP(it, mid+1) {
                        if (!nope[gt[it]]) go.pb(gt[it]);
                    }
                    go.pb(v);
                    if (ask(v,x,go)) {
                        // i can take fewer
                        r = mid;
                    }else{
                        l = mid+1;
                    }
                }
                int yo = gt[l];
                answer(v,yo);
                findculprit(v, yo, from[yo]);
                vector<int> underyo;
                dfs(yo, from[yo], underyo);
                for (int ele : underyo) {
                    nope[ele] = 1;
                }
                for (L = l; L < SZ(gt) && nope[gt[L]]; ++L);
            }
        }

    }
}



void Detect(int T, int N) {
    n=N;
    buildtree();
    vector<int> dord;
    dfs(0, -1, dord);
    REP(i,n) {
        int v = dord[i];
        if (deg[v] < 7) {
            // sneaky!!!
            // i can do more pruning later
            for (int u : tree[v]) {
                {
                    findculprit(v,u,v);
                }
            }
        }
    }
}

#ifdef BALBIT
signed main(){
    IOS();
    vector<pii> edges = {{0,4}, {0,2}, {1,2}, {1,3}, {2,5}, {4,6}, {4,7}, {3,4}, {2,7}};
    REP(i, SZ(edges)) {
        gra[edges[i].f].pb(edges[i].s);
        gra[edges[i].s].pb(edges[i].f);
    }
    int N = 8;
    Detect(-1, N);

}
#endif

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23