oj.uz

답안 #714977

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
714977 2023-03-25T15:46:12 Z dxz05 자매 도시 (APIO20_swap) C++17
17 / 100
 2000 ms 509216 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MaxN = 100002;
const int MaxM = 100002;

int N, M;
const int blockLength = 650;

struct Set{
    int parent;
    bool line;
    pair<int, int> tail;
    Set(){};
    Set(int i){
        parent = i;
        line = true;
        tail = make_pair(i, i);
    }
};

Set t[MaxN];

int MAGIC;
bool flag[MaxN];
Set mem[MaxN][MaxM / blockLength + 3];

int re[MaxN];
int _nxt;

int leader(int x){
    if (MAGIC != -1 && !flag[x]){
        t[x] = (MAGIC == 0 ? Set(x) : mem[x][MAGIC - 1]);
        flag[x] = true;
        re[_nxt++] = x;
    }
    return t[x].parent == x ? x : t[x].parent = leader(t[x].parent);
}

void unite(int x, int y){
    int X = x, Y = y;
    x = leader(x);
    y = leader(y);

    if (rng() & 1){
        swap(x, y);
        swap(X, Y);
    }

    if (x == y){
        t[y].line = false;
        return;
    }

    t[x].parent = y;
    if (!t[x].line){
        t[y].line = false;
        return;
    }

    if (!t[y].line) return;

    if (t[x].tail.first != X && t[x].tail.second != X){
        t[y].line = false;
        return;
    }

    if (t[y].tail.first != Y && t[y].tail.second != Y){
        t[y].line = false;
        return;
    }

    pair<int, int> new_tail;
    new_tail.first = t[x].tail.first ^ t[x].tail.second ^ X;
    new_tail.second = t[y].tail.first ^ t[y].tail.second ^ Y;

    t[y].tail = new_tail;
}

int el[MaxM], er[MaxM];

int blockCount;

tuple<int, int, int> edges[MaxM];
void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
    N = _N, M = _M;

    for (int i = 0; i < M; i++){
        edges[i] = make_tuple(W[i], U[i], V[i]);
    }

    sort(edges, edges + M);

    for (int i = 0; i < N; i++) t[i] = Set(i);

    MAGIC = -1;
    blockCount = 0;

    for (int i = 0; i < M; i++){
        int u = get<1>(edges[i]), v = get<2>(edges[i]);
        unite(u, v);

        if ((i + 1) % blockLength == 0 || i == M - 1){
            int id = blockCount++;

            el[id] = 0, er[id] = i;
            if (id > 0) el[id] = er[id - 1] + 1;

            for (int j = 0; j < N; j++) mem[j][id] = t[leader(j)];
        }

    }

    for (int i = 0; i < N; i++) flag[i] = false;
}

bool can(int x, int y){
    x = leader(x);
    y = leader(y);
    return x == y && !t[x].line;
}

int getMinimumFuelCapacity(int X, int Y) {
    int id = 0;
    while (id < blockCount){
        int xx = mem[X][id].parent, yy = mem[Y][id].parent;
        if (xx == yy && !mem[xx][id].line){
            break;
        } else {
            id++;
        }
    }

    if (id == blockCount) return -1;

    MAGIC = id;

    int ans = -1;

    _nxt = 0;

    for (int i = el[id]; i <= er[id]; i++){
        auto [w, u, v] = edges[i];
        unite(u, v);
        if (can(X, Y)){
            ans = w;
            break;
        }
    }

    for (int i = 0; i < _nxt; i++) flag[re[i]] = false;

    return ans;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 246092 KB Output is correct
2 Correct 121 ms 246020 KB Output is correct
3 Correct 108 ms 246056 KB Output is correct
4 Correct 114 ms 246016 KB Output is correct
5 Correct 122 ms 246100 KB Output is correct
6 Correct 128 ms 246016 KB Output is correct
7 Correct 118 ms 246028 KB Output is correct
8 Correct 111 ms 246132 KB Output is correct
9 Correct 309 ms 248908 KB Output is correct
10 Correct 417 ms 249500 KB Output is correct
11 Correct 392 ms 249448 KB Output is correct
12 Correct 444 ms 249644 KB Output is correct
13 Correct 455 ms 249636 KB Output is correct
14 Correct 310 ms 249064 KB Output is correct
15 Correct 590 ms 251356 KB Output is correct
16 Correct 535 ms 251260 KB Output is correct
17 Correct 594 ms 251380 KB Output is correct
18 Correct 570 ms 251412 KB Output is correct
19 Execution timed out 2067 ms 248512 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 246092 KB Output is correct
2 Correct 121 ms 246020 KB Output is correct
3 Execution timed out 2059 ms 250976 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 246092 KB Output is correct
2 Correct 121 ms 246020 KB Output is correct
3 Correct 108 ms 246056 KB Output is correct
4 Correct 114 ms 246016 KB Output is correct
5 Correct 122 ms 246100 KB Output is correct
6 Correct 128 ms 246016 KB Output is correct
7 Correct 118 ms 246028 KB Output is correct
8 Correct 111 ms 246132 KB Output is correct
9 Correct 113 ms 245988 KB Output is correct
10 Correct 115 ms 246116 KB Output is correct
11 Correct 122 ms 246124 KB Output is correct
12 Correct 112 ms 246032 KB Output is correct
13 Correct 131 ms 246120 KB Output is correct
14 Correct 116 ms 246104 KB Output is correct
15 Correct 113 ms 246092 KB Output is correct
16 Correct 114 ms 246124 KB Output is correct
17 Correct 117 ms 246140 KB Output is correct
18 Correct 137 ms 246136 KB Output is correct
19 Correct 136 ms 246060 KB Output is correct
20 Correct 140 ms 246104 KB Output is correct
21 Correct 154 ms 246112 KB Output is correct
22 Correct 139 ms 246092 KB Output is correct
23 Correct 141 ms 246076 KB Output is correct
24 Correct 153 ms 246092 KB Output is correct
25 Correct 129 ms 246096 KB Output is correct
26 Correct 109 ms 246204 KB Output is correct
27 Correct 114 ms 246020 KB Output is correct
28 Correct 117 ms 246092 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 245988 KB Output is correct
2 Correct 129 ms 246092 KB Output is correct
3 Correct 121 ms 246020 KB Output is correct
4 Correct 108 ms 246056 KB Output is correct
5 Correct 114 ms 246016 KB Output is correct
6 Correct 122 ms 246100 KB Output is correct
7 Correct 128 ms 246016 KB Output is correct
8 Correct 118 ms 246028 KB Output is correct
9 Correct 111 ms 246132 KB Output is correct
10 Correct 309 ms 248908 KB Output is correct
11 Correct 417 ms 249500 KB Output is correct
12 Correct 392 ms 249448 KB Output is correct
13 Correct 444 ms 249644 KB Output is correct
14 Correct 455 ms 249636 KB Output is correct
15 Correct 115 ms 246116 KB Output is correct
16 Correct 122 ms 246124 KB Output is correct
17 Correct 112 ms 246032 KB Output is correct
18 Correct 131 ms 246120 KB Output is correct
19 Correct 116 ms 246104 KB Output is correct
20 Correct 113 ms 246092 KB Output is correct
21 Correct 114 ms 246124 KB Output is correct
22 Correct 117 ms 246140 KB Output is correct
23 Correct 137 ms 246136 KB Output is correct
24 Correct 136 ms 246060 KB Output is correct
25 Correct 140 ms 246104 KB Output is correct
26 Correct 154 ms 246112 KB Output is correct
27 Correct 139 ms 246092 KB Output is correct
28 Correct 141 ms 246076 KB Output is correct
29 Correct 153 ms 246092 KB Output is correct
30 Correct 129 ms 246096 KB Output is correct
31 Correct 109 ms 246204 KB Output is correct
32 Correct 114 ms 246020 KB Output is correct
33 Correct 117 ms 246092 KB Output is correct
34 Correct 127 ms 246512 KB Output is correct
35 Correct 445 ms 249676 KB Output is correct
36 Correct 417 ms 249636 KB Output is correct
37 Correct 428 ms 249640 KB Output is correct
38 Correct 439 ms 249592 KB Output is correct
39 Correct 443 ms 249568 KB Output is correct
40 Correct 401 ms 249420 KB Output is correct
41 Correct 476 ms 249632 KB Output is correct
42 Correct 435 ms 249712 KB Output is correct
43 Correct 403 ms 249636 KB Output is correct
44 Correct 456 ms 249636 KB Output is correct
45 Runtime error 658 ms 509216 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 246092 KB Output is correct
2 Correct 121 ms 246020 KB Output is correct
3 Correct 108 ms 246056 KB Output is correct
4 Correct 114 ms 246016 KB Output is correct
5 Correct 122 ms 246100 KB Output is correct
6 Correct 128 ms 246016 KB Output is correct
7 Correct 118 ms 246028 KB Output is correct
8 Correct 111 ms 246132 KB Output is correct
9 Correct 309 ms 248908 KB Output is correct
10 Correct 417 ms 249500 KB Output is correct
11 Correct 392 ms 249448 KB Output is correct
12 Correct 444 ms 249644 KB Output is correct
13 Correct 455 ms 249636 KB Output is correct
14 Correct 310 ms 249064 KB Output is correct
15 Correct 590 ms 251356 KB Output is correct
16 Correct 535 ms 251260 KB Output is correct
17 Correct 594 ms 251380 KB Output is correct
18 Correct 570 ms 251412 KB Output is correct
19 Execution timed out 2059 ms 250976 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 245988 KB Output is correct
2 Correct 129 ms 246092 KB Output is correct
3 Correct 121 ms 246020 KB Output is correct
4 Correct 108 ms 246056 KB Output is correct
5 Correct 114 ms 246016 KB Output is correct
6 Correct 122 ms 246100 KB Output is correct
7 Correct 128 ms 246016 KB Output is correct
8 Correct 118 ms 246028 KB Output is correct
9 Correct 111 ms 246132 KB Output is correct
10 Correct 309 ms 248908 KB Output is correct
11 Correct 417 ms 249500 KB Output is correct
12 Correct 392 ms 249448 KB Output is correct
13 Correct 444 ms 249644 KB Output is correct
14 Correct 455 ms 249636 KB Output is correct
15 Correct 310 ms 249064 KB Output is correct
16 Correct 590 ms 251356 KB Output is correct
17 Correct 535 ms 251260 KB Output is correct
18 Correct 594 ms 251380 KB Output is correct
19 Correct 570 ms 251412 KB Output is correct
20 Execution timed out 2059 ms 250976 KB Time limit exceeded
21 Halted 0 ms 0 KB -