oj.uz

답안 #714972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
714972 2023-03-25T15:41:07 Z dxz05 자매 도시 (APIO20_swap) C++17
37 / 100
 2000 ms 459972 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 = 200002;

int N, M;
const int blockLength = 700;

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 205 ms 452764 KB Output is correct
2 Correct 209 ms 452744 KB Output is correct
3 Correct 200 ms 452684 KB Output is correct
4 Correct 204 ms 452824 KB Output is correct
5 Correct 208 ms 452724 KB Output is correct
6 Correct 207 ms 452816 KB Output is correct
7 Correct 211 ms 452812 KB Output is correct
8 Correct 218 ms 452812 KB Output is correct
9 Correct 396 ms 456208 KB Output is correct
10 Correct 570 ms 456820 KB Output is correct
11 Correct 517 ms 456792 KB Output is correct
12 Correct 598 ms 456964 KB Output is correct
13 Correct 571 ms 456964 KB Output is correct
14 Correct 449 ms 456416 KB Output is correct
15 Correct 730 ms 458552 KB Output is correct
16 Correct 676 ms 458500 KB Output is correct
17 Correct 787 ms 458592 KB Output is correct
18 Correct 718 ms 458576 KB Output is correct
19 Execution timed out 2080 ms 455664 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 452764 KB Output is correct
2 Correct 209 ms 452744 KB Output is correct
3 Execution timed out 2070 ms 458196 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 452764 KB Output is correct
2 Correct 209 ms 452744 KB Output is correct
3 Correct 200 ms 452684 KB Output is correct
4 Correct 204 ms 452824 KB Output is correct
5 Correct 208 ms 452724 KB Output is correct
6 Correct 207 ms 452816 KB Output is correct
7 Correct 211 ms 452812 KB Output is correct
8 Correct 218 ms 452812 KB Output is correct
9 Correct 207 ms 452664 KB Output is correct
10 Correct 205 ms 452788 KB Output is correct
11 Correct 220 ms 452744 KB Output is correct
12 Correct 205 ms 452820 KB Output is correct
13 Correct 214 ms 452756 KB Output is correct
14 Correct 204 ms 452700 KB Output is correct
15 Correct 204 ms 452732 KB Output is correct
16 Correct 202 ms 452816 KB Output is correct
17 Correct 216 ms 452748 KB Output is correct
18 Correct 204 ms 452880 KB Output is correct
19 Correct 204 ms 452788 KB Output is correct
20 Correct 197 ms 452812 KB Output is correct
21 Correct 203 ms 452784 KB Output is correct
22 Correct 201 ms 452804 KB Output is correct
23 Correct 205 ms 452812 KB Output is correct
24 Correct 205 ms 452844 KB Output is correct
25 Correct 212 ms 452876 KB Output is correct
26 Correct 216 ms 452808 KB Output is correct
27 Correct 205 ms 452776 KB Output is correct
28 Correct 202 ms 452808 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 452664 KB Output is correct
2 Correct 205 ms 452764 KB Output is correct
3 Correct 209 ms 452744 KB Output is correct
4 Correct 200 ms 452684 KB Output is correct
5 Correct 204 ms 452824 KB Output is correct
6 Correct 208 ms 452724 KB Output is correct
7 Correct 207 ms 452816 KB Output is correct
8 Correct 211 ms 452812 KB Output is correct
9 Correct 218 ms 452812 KB Output is correct
10 Correct 396 ms 456208 KB Output is correct
11 Correct 570 ms 456820 KB Output is correct
12 Correct 517 ms 456792 KB Output is correct
13 Correct 598 ms 456964 KB Output is correct
14 Correct 571 ms 456964 KB Output is correct
15 Correct 205 ms 452788 KB Output is correct
16 Correct 220 ms 452744 KB Output is correct
17 Correct 205 ms 452820 KB Output is correct
18 Correct 214 ms 452756 KB Output is correct
19 Correct 204 ms 452700 KB Output is correct
20 Correct 204 ms 452732 KB Output is correct
21 Correct 202 ms 452816 KB Output is correct
22 Correct 216 ms 452748 KB Output is correct
23 Correct 204 ms 452880 KB Output is correct
24 Correct 204 ms 452788 KB Output is correct
25 Correct 197 ms 452812 KB Output is correct
26 Correct 203 ms 452784 KB Output is correct
27 Correct 201 ms 452804 KB Output is correct
28 Correct 205 ms 452812 KB Output is correct
29 Correct 205 ms 452844 KB Output is correct
30 Correct 212 ms 452876 KB Output is correct
31 Correct 216 ms 452808 KB Output is correct
32 Correct 205 ms 452776 KB Output is correct
33 Correct 202 ms 452808 KB Output is correct
34 Correct 215 ms 453252 KB Output is correct
35 Correct 509 ms 456548 KB Output is correct
36 Correct 512 ms 456524 KB Output is correct
37 Correct 508 ms 456564 KB Output is correct
38 Correct 619 ms 456400 KB Output is correct
39 Correct 603 ms 456464 KB Output is correct
40 Correct 540 ms 456084 KB Output is correct
41 Correct 549 ms 456440 KB Output is correct
42 Correct 508 ms 456440 KB Output is correct
43 Correct 513 ms 456444 KB Output is correct
44 Correct 527 ms 456440 KB Output is correct
45 Correct 626 ms 458216 KB Output is correct
46 Correct 526 ms 456508 KB Output is correct
47 Correct 524 ms 456448 KB Output is correct
48 Correct 581 ms 456848 KB Output is correct
49 Correct 271 ms 458444 KB Output is correct
50 Correct 261 ms 457136 KB Output is correct
51 Correct 515 ms 457456 KB Output is correct
52 Correct 773 ms 458604 KB Output is correct
53 Correct 841 ms 459216 KB Output is correct
54 Correct 864 ms 459972 KB Output is correct
55 Correct 521 ms 456440 KB Output is correct
56 Correct 792 ms 458964 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 452764 KB Output is correct
2 Correct 209 ms 452744 KB Output is correct
3 Correct 200 ms 452684 KB Output is correct
4 Correct 204 ms 452824 KB Output is correct
5 Correct 208 ms 452724 KB Output is correct
6 Correct 207 ms 452816 KB Output is correct
7 Correct 211 ms 452812 KB Output is correct
8 Correct 218 ms 452812 KB Output is correct
9 Correct 396 ms 456208 KB Output is correct
10 Correct 570 ms 456820 KB Output is correct
11 Correct 517 ms 456792 KB Output is correct
12 Correct 598 ms 456964 KB Output is correct
13 Correct 571 ms 456964 KB Output is correct
14 Correct 449 ms 456416 KB Output is correct
15 Correct 730 ms 458552 KB Output is correct
16 Correct 676 ms 458500 KB Output is correct
17 Correct 787 ms 458592 KB Output is correct
18 Correct 718 ms 458576 KB Output is correct
19 Execution timed out 2070 ms 458196 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 452664 KB Output is correct
2 Correct 205 ms 452764 KB Output is correct
3 Correct 209 ms 452744 KB Output is correct
4 Correct 200 ms 452684 KB Output is correct
5 Correct 204 ms 452824 KB Output is correct
6 Correct 208 ms 452724 KB Output is correct
7 Correct 207 ms 452816 KB Output is correct
8 Correct 211 ms 452812 KB Output is correct
9 Correct 218 ms 452812 KB Output is correct
10 Correct 396 ms 456208 KB Output is correct
11 Correct 570 ms 456820 KB Output is correct
12 Correct 517 ms 456792 KB Output is correct
13 Correct 598 ms 456964 KB Output is correct
14 Correct 571 ms 456964 KB Output is correct
15 Correct 449 ms 456416 KB Output is correct
16 Correct 730 ms 458552 KB Output is correct
17 Correct 676 ms 458500 KB Output is correct
18 Correct 787 ms 458592 KB Output is correct
19 Correct 718 ms 458576 KB Output is correct
20 Execution timed out 2070 ms 458196 KB Time limit exceeded
21 Halted 0 ms 0 KB -