oj.uz

Submission #714947

# Submission time Handle Problem Language Result Execution time Memory
714947 2023-03-25T14:43:39 Z dxz05 Swapping Cities (APIO20_swap) C++17
0 / 100
 630 ms 422360 KB 
#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

const int MaxN = 100005;

int N, M;
const int blockLength = 800;

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][MaxN / blockLength + 4];

vector<int> re; /// Todo: change to static array

int leader(int x){
    if (MAGIC != -1 && !flag[x]){
        t[x] = (MAGIC == 0 ? Set(x) : mem[x][MAGIC - 1]);
        flag[x] = true;
        re.push_back(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 (x == y){
        t[y].line = false;
        return;
    }

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

    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[MaxN], er[MaxN];

int blockCount;

vector<tuple<int, int, int>> edges;
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.emplace_back(W[i], U[i], V[i]);
    }

    sort(edges.begin(), edges.end());

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

    MAGIC = -1;
    blockCount = 0;

    for (int i = 0; i < M; i++){
        unite(U[i], V[i]);

        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;

    re.clear();

    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 : re) flag[i] = false;

    assert(ans != -1);

    return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 203776 KB Output is correct
2 Correct 79 ms 203828 KB Output is correct
3 Correct 78 ms 203784 KB Output is correct
4 Correct 78 ms 203736 KB Output is correct
5 Correct 85 ms 203812 KB Output is correct
6 Correct 87 ms 203768 KB Output is correct
7 Correct 80 ms 203968 KB Output is correct
8 Correct 81 ms 203852 KB Output is correct
9 Correct 254 ms 207264 KB Output is correct
10 Correct 351 ms 207668 KB Output is correct
11 Correct 365 ms 207632 KB Output is correct
12 Correct 353 ms 207816 KB Output is correct
13 Correct 440 ms 207812 KB Output is correct
14 Correct 253 ms 207444 KB Output is correct
15 Correct 479 ms 209312 KB Output is correct
16 Correct 468 ms 209176 KB Output is correct
17 Correct 535 ms 209488 KB Output is correct
18 Correct 551 ms 209352 KB Output is correct
19 Runtime error 276 ms 418300 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 203776 KB Output is correct
2 Correct 79 ms 203828 KB Output is correct
3 Runtime error 630 ms 422360 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 203776 KB Output is correct
2 Correct 79 ms 203828 KB Output is correct
3 Correct 78 ms 203784 KB Output is correct
4 Correct 78 ms 203736 KB Output is correct
5 Correct 85 ms 203812 KB Output is correct
6 Correct 87 ms 203768 KB Output is correct
7 Correct 80 ms 203968 KB Output is correct
8 Correct 81 ms 203852 KB Output is correct
9 Correct 88 ms 203812 KB Output is correct
10 Runtime error 273 ms 413156 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 203812 KB Output is correct
2 Correct 77 ms 203776 KB Output is correct
3 Correct 79 ms 203828 KB Output is correct
4 Correct 78 ms 203784 KB Output is correct
5 Correct 78 ms 203736 KB Output is correct
6 Correct 85 ms 203812 KB Output is correct
7 Correct 87 ms 203768 KB Output is correct
8 Correct 80 ms 203968 KB Output is correct
9 Correct 81 ms 203852 KB Output is correct
10 Correct 254 ms 207264 KB Output is correct
11 Correct 351 ms 207668 KB Output is correct
12 Correct 365 ms 207632 KB Output is correct
13 Correct 353 ms 207816 KB Output is correct
14 Correct 440 ms 207812 KB Output is correct
15 Runtime error 273 ms 413156 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 203776 KB Output is correct
2 Correct 79 ms 203828 KB Output is correct
3 Correct 78 ms 203784 KB Output is correct
4 Correct 78 ms 203736 KB Output is correct
5 Correct 85 ms 203812 KB Output is correct
6 Correct 87 ms 203768 KB Output is correct
7 Correct 80 ms 203968 KB Output is correct
8 Correct 81 ms 203852 KB Output is correct
9 Correct 254 ms 207264 KB Output is correct
10 Correct 351 ms 207668 KB Output is correct
11 Correct 365 ms 207632 KB Output is correct
12 Correct 353 ms 207816 KB Output is correct
13 Correct 440 ms 207812 KB Output is correct
14 Correct 253 ms 207444 KB Output is correct
15 Correct 479 ms 209312 KB Output is correct
16 Correct 468 ms 209176 KB Output is correct
17 Correct 535 ms 209488 KB Output is correct
18 Correct 551 ms 209352 KB Output is correct
19 Runtime error 630 ms 422360 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 203812 KB Output is correct
2 Correct 77 ms 203776 KB Output is correct
3 Correct 79 ms 203828 KB Output is correct
4 Correct 78 ms 203784 KB Output is correct
5 Correct 78 ms 203736 KB Output is correct
6 Correct 85 ms 203812 KB Output is correct
7 Correct 87 ms 203768 KB Output is correct
8 Correct 80 ms 203968 KB Output is correct
9 Correct 81 ms 203852 KB Output is correct
10 Correct 254 ms 207264 KB Output is correct
11 Correct 351 ms 207668 KB Output is correct
12 Correct 365 ms 207632 KB Output is correct
13 Correct 353 ms 207816 KB Output is correct
14 Correct 440 ms 207812 KB Output is correct
15 Correct 253 ms 207444 KB Output is correct
16 Correct 479 ms 209312 KB Output is correct
17 Correct 468 ms 209176 KB Output is correct
18 Correct 535 ms 209488 KB Output is correct
19 Correct 551 ms 209352 KB Output is correct
20 Runtime error 630 ms 422360 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -