oj.uz

Submission #714969

# Submission time Handle Problem Language Result Execution time Memory
714969 2023-03-25T15:39:54 Z dxz05 Swapping Cities (APIO20_swap) C++17
37 / 100
 2000 ms 362204 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 = 900;

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

# Verdict Execution time Memory Grader output
1 Correct 163 ms 354120 KB Output is correct
2 Correct 164 ms 354092 KB Output is correct
3 Correct 159 ms 354124 KB Output is correct
4 Correct 157 ms 354212 KB Output is correct
5 Correct 157 ms 354100 KB Output is correct
6 Correct 158 ms 354112 KB Output is correct
7 Correct 160 ms 354120 KB Output is correct
8 Correct 176 ms 354060 KB Output is correct
9 Correct 309 ms 356948 KB Output is correct
10 Correct 371 ms 357576 KB Output is correct
11 Correct 373 ms 357604 KB Output is correct
12 Correct 402 ms 357756 KB Output is correct
13 Correct 420 ms 357736 KB Output is correct
14 Correct 311 ms 357056 KB Output is correct
15 Correct 517 ms 359408 KB Output is correct
16 Correct 588 ms 359292 KB Output is correct
17 Correct 719 ms 359476 KB Output is correct
18 Correct 675 ms 359572 KB Output is correct
19 Execution timed out 2072 ms 356424 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 354120 KB Output is correct
2 Correct 164 ms 354092 KB Output is correct
3 Execution timed out 2075 ms 359024 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 354120 KB Output is correct
2 Correct 164 ms 354092 KB Output is correct
3 Correct 159 ms 354124 KB Output is correct
4 Correct 157 ms 354212 KB Output is correct
5 Correct 157 ms 354100 KB Output is correct
6 Correct 158 ms 354112 KB Output is correct
7 Correct 160 ms 354120 KB Output is correct
8 Correct 176 ms 354060 KB Output is correct
9 Correct 178 ms 354124 KB Output is correct
10 Correct 178 ms 354152 KB Output is correct
11 Correct 172 ms 354076 KB Output is correct
12 Correct 192 ms 354228 KB Output is correct
13 Correct 170 ms 354132 KB Output is correct
14 Correct 166 ms 354056 KB Output is correct
15 Correct 173 ms 354140 KB Output is correct
16 Correct 200 ms 354140 KB Output is correct
17 Correct 188 ms 354152 KB Output is correct
18 Correct 188 ms 354092 KB Output is correct
19 Correct 233 ms 354108 KB Output is correct
20 Correct 163 ms 354100 KB Output is correct
21 Correct 167 ms 354172 KB Output is correct
22 Correct 190 ms 354108 KB Output is correct
23 Correct 162 ms 354132 KB Output is correct
24 Correct 180 ms 354188 KB Output is correct
25 Correct 183 ms 354144 KB Output is correct
26 Correct 169 ms 354244 KB Output is correct
27 Correct 163 ms 354104 KB Output is correct
28 Correct 176 ms 354220 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 354124 KB Output is correct
2 Correct 163 ms 354120 KB Output is correct
3 Correct 164 ms 354092 KB Output is correct
4 Correct 159 ms 354124 KB Output is correct
5 Correct 157 ms 354212 KB Output is correct
6 Correct 157 ms 354100 KB Output is correct
7 Correct 158 ms 354112 KB Output is correct
8 Correct 160 ms 354120 KB Output is correct
9 Correct 176 ms 354060 KB Output is correct
10 Correct 309 ms 356948 KB Output is correct
11 Correct 371 ms 357576 KB Output is correct
12 Correct 373 ms 357604 KB Output is correct
13 Correct 402 ms 357756 KB Output is correct
14 Correct 420 ms 357736 KB Output is correct
15 Correct 178 ms 354152 KB Output is correct
16 Correct 172 ms 354076 KB Output is correct
17 Correct 192 ms 354228 KB Output is correct
18 Correct 170 ms 354132 KB Output is correct
19 Correct 166 ms 354056 KB Output is correct
20 Correct 173 ms 354140 KB Output is correct
21 Correct 200 ms 354140 KB Output is correct
22 Correct 188 ms 354152 KB Output is correct
23 Correct 188 ms 354092 KB Output is correct
24 Correct 233 ms 354108 KB Output is correct
25 Correct 163 ms 354100 KB Output is correct
26 Correct 167 ms 354172 KB Output is correct
27 Correct 190 ms 354108 KB Output is correct
28 Correct 162 ms 354132 KB Output is correct
29 Correct 180 ms 354188 KB Output is correct
30 Correct 183 ms 354144 KB Output is correct
31 Correct 169 ms 354244 KB Output is correct
32 Correct 163 ms 354104 KB Output is correct
33 Correct 176 ms 354220 KB Output is correct
34 Correct 198 ms 354896 KB Output is correct
35 Correct 411 ms 358676 KB Output is correct
36 Correct 457 ms 358736 KB Output is correct
37 Correct 412 ms 358668 KB Output is correct
38 Correct 411 ms 358732 KB Output is correct
39 Correct 418 ms 358668 KB Output is correct
40 Correct 381 ms 358320 KB Output is correct
41 Correct 471 ms 358772 KB Output is correct
42 Correct 410 ms 358680 KB Output is correct
43 Correct 449 ms 358720 KB Output is correct
44 Correct 403 ms 358776 KB Output is correct
45 Correct 468 ms 360372 KB Output is correct
46 Correct 445 ms 358676 KB Output is correct
47 Correct 404 ms 358732 KB Output is correct
48 Correct 449 ms 359068 KB Output is correct
49 Correct 270 ms 360616 KB Output is correct
50 Correct 231 ms 359384 KB Output is correct
51 Correct 449 ms 359684 KB Output is correct
52 Correct 585 ms 360840 KB Output is correct
53 Correct 651 ms 361504 KB Output is correct
54 Correct 667 ms 362204 KB Output is correct
55 Correct 432 ms 358528 KB Output is correct
56 Correct 650 ms 361052 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 354120 KB Output is correct
2 Correct 164 ms 354092 KB Output is correct
3 Correct 159 ms 354124 KB Output is correct
4 Correct 157 ms 354212 KB Output is correct
5 Correct 157 ms 354100 KB Output is correct
6 Correct 158 ms 354112 KB Output is correct
7 Correct 160 ms 354120 KB Output is correct
8 Correct 176 ms 354060 KB Output is correct
9 Correct 309 ms 356948 KB Output is correct
10 Correct 371 ms 357576 KB Output is correct
11 Correct 373 ms 357604 KB Output is correct
12 Correct 402 ms 357756 KB Output is correct
13 Correct 420 ms 357736 KB Output is correct
14 Correct 311 ms 357056 KB Output is correct
15 Correct 517 ms 359408 KB Output is correct
16 Correct 588 ms 359292 KB Output is correct
17 Correct 719 ms 359476 KB Output is correct
18 Correct 675 ms 359572 KB Output is correct
19 Execution timed out 2075 ms 359024 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 354124 KB Output is correct
2 Correct 163 ms 354120 KB Output is correct
3 Correct 164 ms 354092 KB Output is correct
4 Correct 159 ms 354124 KB Output is correct
5 Correct 157 ms 354212 KB Output is correct
6 Correct 157 ms 354100 KB Output is correct
7 Correct 158 ms 354112 KB Output is correct
8 Correct 160 ms 354120 KB Output is correct
9 Correct 176 ms 354060 KB Output is correct
10 Correct 309 ms 356948 KB Output is correct
11 Correct 371 ms 357576 KB Output is correct
12 Correct 373 ms 357604 KB Output is correct
13 Correct 402 ms 357756 KB Output is correct
14 Correct 420 ms 357736 KB Output is correct
15 Correct 311 ms 357056 KB Output is correct
16 Correct 517 ms 359408 KB Output is correct
17 Correct 588 ms 359292 KB Output is correct
18 Correct 719 ms 359476 KB Output is correct
19 Correct 675 ms 359572 KB Output is correct
20 Execution timed out 2075 ms 359024 KB Time limit exceeded
21 Halted 0 ms 0 KB -