Submission #1282718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282718		nikaa123	Park (JOI17_park)	C++17	0 / 100	2 ms	572 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1505;
int f[MAXN];
int n;
static int p[MAXN];

vector<int> lst, nodes, vis(MAXN);
vector<vector<int>> v(MAXN);

void colect(int x) {
    if (vis[x]) return;
    nodes.push_back(x);
    vis[x] = 1;
    vector<int> children = v[x];
    sort(children.begin(), children.end()); // deterministic traversal
    for (auto to : children) {
        if (f[to] && !vis[to]) colect(to);
    }
}

void dfs(int x, int node) {
    sort(v[x].begin(), v[x].end()); // deterministic
    while (true) {
        if (vis[x]) return;
        nodes.clear();
        for (int i = 0; i < n; ++i) vis[i] = 0;
        colect(x);
        if (nodes.empty()) return; // safety
        for (int i = 0; i < n; i++) p[i] = 0;
        for (auto to : nodes) p[to] = 1;
        p[node] = p[x] = 1;

        if (!Ask(min(node, x), max(node, x), p)) return;

        int l = 0, r = (int)nodes.size() - 1;
        int res = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            for (int i = 0; i < n; ++i) p[i] = 0;
            for (int i = 0; i <= mid; ++i) p[nodes[i]] = 1;
            p[node] = p[x] = 1;
            if (Ask(min(node, x), max(node, x), p)) {
                res = nodes[mid];
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        if (res == -1) return; // safety
        vis[res] = 1;
        lst.push_back(res);
        for (auto to : v[res]) {
            dfs(to, node);
        }
    }
}

void explore(int x) {
    if (f[x]) return;

    for (int i = 0; i < n; i++) p[i] = f[i];
    p[x] = 1;
    p[0] = 1;

    while (!Ask(0, x, p)) {
        int l = 0, r = n - 1, res = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            for (int i = 0; i < n; ++i)
                p[i] = (f[i] || i <= mid) ? 1 : 0;
            p[x] = 1;
            p[0] = 1;
            if (Ask(0, x, p)) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (res < 0 || res >= n) return; // safety
        explore(res);
    }

    for (int i = 0; i < n; ++i) vis[i] = 0;
    lst.clear();
    dfs(0, x);

    for (auto u : lst) {
        Answer(min(u, x), max(u, x));
    }
    if (!lst.empty()) v[lst[0]].push_back(x);
    f[x] = 1;
}

void Detect(int T, int N) {
    n = N;
    for (int i = 0; i < MAXN; i++) {
        f[i] = 0;
        p[i] = 0;
        vis[i] = 0;
        v[i].clear();
    }
    f[0] = 1;
    for (int i = 0; i < n; i++) {
        if (!f[i]) explore(i);
    }
}

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