oj.uz

Submission #714951

# Submission time Handle Problem Language Result Execution time Memory
714951 2023-03-25T14:56:37 Z dxz05 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 327056 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 = 1000;

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 124 ms 321160 KB Output is correct
2 Correct 126 ms 321148 KB Output is correct
3 Correct 130 ms 321268 KB Output is correct
4 Correct 127 ms 321228 KB Output is correct
5 Correct 126 ms 321252 KB Output is correct
6 Correct 139 ms 321196 KB Output is correct
7 Correct 125 ms 321240 KB Output is correct
8 Correct 134 ms 321260 KB Output is correct
9 Correct 286 ms 325156 KB Output is correct
10 Correct 349 ms 325408 KB Output is correct
11 Correct 327 ms 325436 KB Output is correct
12 Correct 388 ms 325572 KB Output is correct
13 Correct 472 ms 325572 KB Output is correct
14 Correct 389 ms 325156 KB Output is correct
15 Correct 656 ms 327056 KB Output is correct
16 Correct 653 ms 326984 KB Output is correct
17 Correct 506 ms 327016 KB Output is correct
18 Correct 513 ms 327048 KB Output is correct
19 Execution timed out 2095 ms 324004 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 321160 KB Output is correct
2 Correct 126 ms 321148 KB Output is correct
3 Execution timed out 2092 ms 326868 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 321160 KB Output is correct
2 Correct 126 ms 321148 KB Output is correct
3 Correct 130 ms 321268 KB Output is correct
4 Correct 127 ms 321228 KB Output is correct
5 Correct 126 ms 321252 KB Output is correct
6 Correct 139 ms 321196 KB Output is correct
7 Correct 125 ms 321240 KB Output is correct
8 Correct 134 ms 321260 KB Output is correct
9 Correct 128 ms 321176 KB Output is correct
10 Correct 130 ms 321236 KB Output is correct
11 Correct 129 ms 321316 KB Output is correct
12 Correct 129 ms 321228 KB Output is correct
13 Correct 130 ms 321300 KB Output is correct
14 Correct 131 ms 321292 KB Output is correct
15 Correct 130 ms 321272 KB Output is correct
16 Correct 126 ms 321288 KB Output is correct
17 Correct 127 ms 321288 KB Output is correct
18 Correct 132 ms 321332 KB Output is correct
19 Correct 125 ms 321284 KB Output is correct
20 Correct 122 ms 321288 KB Output is correct
21 Correct 127 ms 321296 KB Output is correct
22 Correct 128 ms 321312 KB Output is correct
23 Correct 125 ms 321204 KB Output is correct
24 Incorrect 126 ms 321276 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 321176 KB Output is correct
2 Correct 124 ms 321160 KB Output is correct
3 Correct 126 ms 321148 KB Output is correct
4 Correct 130 ms 321268 KB Output is correct
5 Correct 127 ms 321228 KB Output is correct
6 Correct 126 ms 321252 KB Output is correct
7 Correct 139 ms 321196 KB Output is correct
8 Correct 125 ms 321240 KB Output is correct
9 Correct 134 ms 321260 KB Output is correct
10 Correct 286 ms 325156 KB Output is correct
11 Correct 349 ms 325408 KB Output is correct
12 Correct 327 ms 325436 KB Output is correct
13 Correct 388 ms 325572 KB Output is correct
14 Correct 472 ms 325572 KB Output is correct
15 Correct 130 ms 321236 KB Output is correct
16 Correct 129 ms 321316 KB Output is correct
17 Correct 129 ms 321228 KB Output is correct
18 Correct 130 ms 321300 KB Output is correct
19 Correct 131 ms 321292 KB Output is correct
20 Correct 130 ms 321272 KB Output is correct
21 Correct 126 ms 321288 KB Output is correct
22 Correct 127 ms 321288 KB Output is correct
23 Correct 132 ms 321332 KB Output is correct
24 Correct 125 ms 321284 KB Output is correct
25 Correct 122 ms 321288 KB Output is correct
26 Correct 127 ms 321296 KB Output is correct
27 Correct 128 ms 321312 KB Output is correct
28 Correct 125 ms 321204 KB Output is correct
29 Incorrect 126 ms 321276 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 321160 KB Output is correct
2 Correct 126 ms 321148 KB Output is correct
3 Correct 130 ms 321268 KB Output is correct
4 Correct 127 ms 321228 KB Output is correct
5 Correct 126 ms 321252 KB Output is correct
6 Correct 139 ms 321196 KB Output is correct
7 Correct 125 ms 321240 KB Output is correct
8 Correct 134 ms 321260 KB Output is correct
9 Correct 286 ms 325156 KB Output is correct
10 Correct 349 ms 325408 KB Output is correct
11 Correct 327 ms 325436 KB Output is correct
12 Correct 388 ms 325572 KB Output is correct
13 Correct 472 ms 325572 KB Output is correct
14 Correct 389 ms 325156 KB Output is correct
15 Correct 656 ms 327056 KB Output is correct
16 Correct 653 ms 326984 KB Output is correct
17 Correct 506 ms 327016 KB Output is correct
18 Correct 513 ms 327048 KB Output is correct
19 Execution timed out 2092 ms 326868 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 321176 KB Output is correct
2 Correct 124 ms 321160 KB Output is correct
3 Correct 126 ms 321148 KB Output is correct
4 Correct 130 ms 321268 KB Output is correct
5 Correct 127 ms 321228 KB Output is correct
6 Correct 126 ms 321252 KB Output is correct
7 Correct 139 ms 321196 KB Output is correct
8 Correct 125 ms 321240 KB Output is correct
9 Correct 134 ms 321260 KB Output is correct
10 Correct 286 ms 325156 KB Output is correct
11 Correct 349 ms 325408 KB Output is correct
12 Correct 327 ms 325436 KB Output is correct
13 Correct 388 ms 325572 KB Output is correct
14 Correct 472 ms 325572 KB Output is correct
15 Correct 389 ms 325156 KB Output is correct
16 Correct 656 ms 327056 KB Output is correct
17 Correct 653 ms 326984 KB Output is correct
18 Correct 506 ms 327016 KB Output is correct
19 Correct 513 ms 327048 KB Output is correct
20 Execution timed out 2092 ms 326868 KB Time limit exceeded
21 Halted 0 ms 0 KB -