oj.uz

Submission #60434

# Submission time Handle Problem Language Result Execution time Memory
60434 2018-07-24T07:52:22 Z 강태규(#1741) Park (JOI17_park) C++11
100 / 100
 555 ms 1412 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 15 ms 612 KB Output is correct
3 Correct 14 ms 612 KB Output is correct
4 Correct 23 ms 648 KB Output is correct
5 Correct 43 ms 648 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 776 KB Output is correct
2 Correct 173 ms 928 KB Output is correct
3 Correct 281 ms 928 KB Output is correct
4 Correct 544 ms 1060 KB Output is correct
5 Correct 555 ms 1112 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 1112 KB Output is correct
2 Correct 349 ms 1112 KB Output is correct
3 Correct 333 ms 1112 KB Output is correct
4 Correct 302 ms 1112 KB Output is correct
5 Correct 367 ms 1112 KB Output is correct
6 Correct 335 ms 1112 KB Output is correct
7 Correct 328 ms 1112 KB Output is correct
8 Correct 355 ms 1112 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 1112 KB Output is correct
2 Correct 427 ms 1112 KB Output is correct
3 Correct 392 ms 1112 KB Output is correct
4 Correct 389 ms 1112 KB Output is correct
5 Correct 486 ms 1152 KB Output is correct
6 Correct 406 ms 1152 KB Output is correct
7 Correct 424 ms 1152 KB Output is correct
8 Correct 399 ms 1152 KB Output is correct
9 Correct 397 ms 1152 KB Output is correct
10 Correct 468 ms 1152 KB Output is correct
11 Correct 409 ms 1152 KB Output is correct
12 Correct 445 ms 1152 KB Output is correct
13 Correct 434 ms 1152 KB Output is correct
14 Correct 406 ms 1152 KB Output is correct
15 Correct 507 ms 1152 KB Output is correct
16 Correct 353 ms 1152 KB Output is correct
17 Correct 552 ms 1152 KB Output is correct
18 Correct 416 ms 1152 KB Output is correct
19 Correct 445 ms 1152 KB Output is correct
20 Correct 370 ms 1152 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 1152 KB Output is correct
2 Correct 487 ms 1152 KB Output is correct
3 Correct 426 ms 1152 KB Output is correct
4 Correct 442 ms 1152 KB Output is correct
5 Correct 478 ms 1176 KB Output is correct
6 Correct 451 ms 1176 KB Output is correct
7 Correct 428 ms 1176 KB Output is correct
8 Correct 487 ms 1176 KB Output is correct
9 Correct 460 ms 1176 KB Output is correct
10 Correct 398 ms 1276 KB Output is correct
11 Correct 433 ms 1276 KB Output is correct
12 Correct 437 ms 1324 KB Output is correct
13 Correct 371 ms 1324 KB Output is correct
14 Correct 434 ms 1372 KB Output is correct
15 Correct 443 ms 1372 KB Output is correct
16 Correct 345 ms 1412 KB Output is correct
17 Correct 544 ms 1412 KB Output is correct
18 Correct 399 ms 1412 KB Output is correct