oj.uz

Submission #60430

# Submission time Handle Problem Language Result Execution time Memory
60430 2018-07-24T07:44:46 Z 강태규(#1741) Park (JOI17_park) C++11
0 / 100
 4 ms 624 KB 
#include "park.h"
#include <vector>

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) 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 = 0, e = n - 1;
    while (s < e) {
        int m = (s + e) / 2;
        init();
        for (int i = 0; i < n; ++i) if (check[i]) place[i] = 1;
        for (int i = 0; i <= m; ++i) if (check[i] != -1) place[i] = 1;
        check[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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Wrong Answer[4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 616 KB Wrong Answer[4]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 616 KB Wrong Answer[4]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 616 KB Wrong Answer[4]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 624 KB Wrong Answer[4]
2 Halted 0 ms 0 KB -