oj.uz

Submission #714952

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

using namespace std;

const int MaxN = 100005;
const int MaxM = 200005;

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

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;

    return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 355660 KB Output is correct
2 Correct 136 ms 355660 KB Output is correct
3 Correct 134 ms 355640 KB Output is correct
4 Correct 141 ms 355660 KB Output is correct
5 Correct 137 ms 355744 KB Output is correct
6 Correct 139 ms 355744 KB Output is correct
7 Correct 141 ms 355736 KB Output is correct
8 Correct 135 ms 355720 KB Output is correct
9 Correct 305 ms 359252 KB Output is correct
10 Correct 392 ms 359600 KB Output is correct
11 Correct 395 ms 359480 KB Output is correct
12 Correct 391 ms 359664 KB Output is correct
13 Correct 426 ms 359620 KB Output is correct
14 Correct 301 ms 359304 KB Output is correct
15 Correct 544 ms 361096 KB Output is correct
16 Correct 524 ms 361044 KB Output is correct
17 Correct 592 ms 361392 KB Output is correct
18 Correct 546 ms 361256 KB Output is correct
19 Execution timed out 2096 ms 358220 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 355660 KB Output is correct
2 Correct 136 ms 355660 KB Output is correct
3 Execution timed out 2084 ms 361060 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 355660 KB Output is correct
2 Correct 136 ms 355660 KB Output is correct
3 Correct 134 ms 355640 KB Output is correct
4 Correct 141 ms 355660 KB Output is correct
5 Correct 137 ms 355744 KB Output is correct
6 Correct 139 ms 355744 KB Output is correct
7 Correct 141 ms 355736 KB Output is correct
8 Correct 135 ms 355720 KB Output is correct
9 Correct 139 ms 355656 KB Output is correct
10 Incorrect 137 ms 355720 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 355656 KB Output is correct
2 Correct 138 ms 355660 KB Output is correct
3 Correct 136 ms 355660 KB Output is correct
4 Correct 134 ms 355640 KB Output is correct
5 Correct 141 ms 355660 KB Output is correct
6 Correct 137 ms 355744 KB Output is correct
7 Correct 139 ms 355744 KB Output is correct
8 Correct 141 ms 355736 KB Output is correct
9 Correct 135 ms 355720 KB Output is correct
10 Correct 305 ms 359252 KB Output is correct
11 Correct 392 ms 359600 KB Output is correct
12 Correct 395 ms 359480 KB Output is correct
13 Correct 391 ms 359664 KB Output is correct
14 Correct 426 ms 359620 KB Output is correct
15 Incorrect 137 ms 355720 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 355660 KB Output is correct
2 Correct 136 ms 355660 KB Output is correct
3 Correct 134 ms 355640 KB Output is correct
4 Correct 141 ms 355660 KB Output is correct
5 Correct 137 ms 355744 KB Output is correct
6 Correct 139 ms 355744 KB Output is correct
7 Correct 141 ms 355736 KB Output is correct
8 Correct 135 ms 355720 KB Output is correct
9 Correct 305 ms 359252 KB Output is correct
10 Correct 392 ms 359600 KB Output is correct
11 Correct 395 ms 359480 KB Output is correct
12 Correct 391 ms 359664 KB Output is correct
13 Correct 426 ms 359620 KB Output is correct
14 Correct 301 ms 359304 KB Output is correct
15 Correct 544 ms 361096 KB Output is correct
16 Correct 524 ms 361044 KB Output is correct
17 Correct 592 ms 361392 KB Output is correct
18 Correct 546 ms 361256 KB Output is correct
19 Execution timed out 2084 ms 361060 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 355656 KB Output is correct
2 Correct 138 ms 355660 KB Output is correct
3 Correct 136 ms 355660 KB Output is correct
4 Correct 134 ms 355640 KB Output is correct
5 Correct 141 ms 355660 KB Output is correct
6 Correct 137 ms 355744 KB Output is correct
7 Correct 139 ms 355744 KB Output is correct
8 Correct 141 ms 355736 KB Output is correct
9 Correct 135 ms 355720 KB Output is correct
10 Correct 305 ms 359252 KB Output is correct
11 Correct 392 ms 359600 KB Output is correct
12 Correct 395 ms 359480 KB Output is correct
13 Correct 391 ms 359664 KB Output is correct
14 Correct 426 ms 359620 KB Output is correct
15 Correct 301 ms 359304 KB Output is correct
16 Correct 544 ms 361096 KB Output is correct
17 Correct 524 ms 361044 KB Output is correct
18 Correct 592 ms 361392 KB Output is correct
19 Correct 546 ms 361256 KB Output is correct
20 Execution timed out 2084 ms 361060 KB Time limit exceeded
21 Halted 0 ms 0 KB -