Submission #1204003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204003		Ghulam_Junaid	Park (JOI17_park)	C++20	67 / 100	123 ms	2888 KiB

park

#include <bits/stdc++.h>
#include "park.h"
// #include "grader.cpp"
using namespace std;
static int Place[1400];

const int MXN = 1405;
int n, par[MXN], h[MXN];
vector<int> g[MXN], lvl[MXN];
vector<pair<int, int>> edges;

int Query(int u, int v){
    Place[u] = Place[v] = 1;
    if (u > v) swap(u, v);
    int res = Ask(u, v, Place);
    memset(Place, 0, sizeof Place);
    return res;
}

void get_path(int u, int v){
    vector<int> nodes;
    for (int x = 0; x < n; x ++){
        if (x == u or x == v) continue;
        nodes.push_back(x);
    }

    if (Query(u, v)){
        g[u].push_back(v);
        g[v].push_back(u);
        edges.push_back({u, v});
        par[v] = u;
        return ;
    }

    int lo = -1;
    int hi = nodes.size() - 1;
    while (hi - lo > 1){
        int mid = (lo + hi) / 2;

        for (int i = 0; i <= mid; i ++)
            Place[nodes[i]] = 1;
        if (Query(u, v))
            hi = mid;
        else
            lo = mid;
    }

    get_path(u, nodes[hi]);
    get_path(nodes[hi], v);
}

int comp(int u, int v, vector<int> vec){
    for (int i = 0; i < n; i ++)
        Place[i] = 1;
    for (int x : vec)
        Place[x] = 0;
    return Query(u, v);
}

void Detect(int T, int nn) {
    n = nn;
    memset(par, -1, sizeof par);
    memset(Place, 0, sizeof Place);

    lvl[h[0]].push_back(0);
    for (int v = 1; v < n; v ++){
        if (g[v].size()) continue;

        int lo = 0, hi = n;
        while (hi - lo > 1){
            int mid = (lo + hi) / 2;

            if (lvl[mid].empty() or comp(0, v, lvl[mid]))
                hi = mid;
            else
                lo = mid;
        }
        int anc_lvl = lo;
        
        lo = -1, hi = lvl[anc_lvl].size() - 1;
        while (hi - lo > 1){
            int mid = (lo + hi) / 2;

            vector<int> vec;
            for (int i = 0; i <= mid; i ++)
                vec.push_back(lvl[anc_lvl][i]);
            
            if (comp(0, v, vec))
                lo = mid;
            else
                hi = mid;
        }

        int anc = lvl[anc_lvl][hi];
        get_path(anc, v);

        int u = v;
        vector<int> path;
        while (u != anc){
            path.push_back(u);
            u = par[u];
        }
        while (path.size()){
            u = path.back();
            path.pop_back();
            h[u] = h[par[u]] + 1;
            lvl[h[u]].push_back(u);
        }
    }

    for (auto [u, v] : edges)
        Answer(min(u, v), max(u, v));
}

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