Submission #250934

#	Time	Username	Problem	Language	Result	Execution time	Memory
250934		imeimi2000	Park (JOI17_park)	C++17	100 / 100	545 ms	788 KiB

park

#include "park.h"
#include <vector>
#include <cstdlib>
 
using namespace std;
 
static int n;
 
static int place[1400];
static int check[1400];
static vector<int> edge[1400];
static int alive[1400];
static int ord[1400];
static int rev[1400];
 
void init() {
    for (int i = 0; i < n; ++i) place[i] = 0;
}
 
int imeAsk(int a, int b) {
    if (a == b) exit(1);
    if (a > b) swap(a, b);
    return Ask(a, b, place);
}
 
int isConnected(int x) {
    init();
    for (int i = 0; i < n; ++i) if (check[i] == 1) place[i] = 1;
    place[x] = 1;
    return imeAsk(0, x);
}
 
int findNearNode(int x) {
    int s = 1, e = n - 1;
    while (s < e) {
        int m = (s + e) / 2;
        init();
        for (int i = 0; i < n; ++i) if (check[i] == 1) place[i] = 1;
        for (int i = 0; i <= m; ++i) if (check[i] != -1) place[i] = 1;
        place[x] = 1;
        if (imeAsk(0, x)) e = m;
        else s = m + 1;
    }
    return s;
}
 
int tp;
void dfs(int x) {
    ord[x] = tp++;
    rev[ord[x]] = x;
    for (int i : edge[x]) {
        if (ord[i] != -1) continue;
        if (alive[i]) dfs(i);
    }
}
 
void del(int x) {
    alive[x] = 0;
    for (int i : edge[x]) {
        if (alive[i]) del(i);
    }
}
 
void findEdges(int x) {
    for (int i = 0; i < n; ++i) alive[i] = (check[i] == 1);
    for (int i = 0; i < n; ++i) {
        while (alive[i]) {
            for (int i = 0; i < n; ++i) ord[i] = -1, rev[i] = -1;
            tp = 0;
            dfs(i);
            for (int i = 0; i < n; ++i) place[i] = (ord[i] != -1);
            place[x] = 1;
            if (!imeAsk(i, x)) {
                del(i);
                break;
            }
            int s = 0, e = tp - 1;
            while (s < e) {
                int m = (s + e) / 2;
                init();
                for (int i = 0; i <= m; ++i) place[rev[i]] = 1;
                place[x] = 1;
                if (imeAsk(i, x)) e = m;
                else s = m + 1;
            }
            edge[rev[s]].push_back(x);
            edge[x].push_back(rev[s]);
            alive[rev[s]] = 0;
        }
    }
}
 
void solve(int x) {
    if (check[x]) return;
    check[x] = -1;
    while (!isConnected(x)) {
        int nxt = findNearNode(x);
        solve(nxt);
    }
    findEdges(x);
    check[x] = 1;
}
 
void Detect(int T, int N) {
    n = N;
    check[0] = 1;
    for (int i = 1; i < n; ++i) solve(i);
    for (int i = 0; i < n; ++i) {
        for (int j : edge[i]) {
            if (i < j) Answer(i, j);
        }
    }
}

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