oj.uz

Submission #714938

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

using namespace std;

const int MaxN = 100005;
vector<tuple<int, int, int>> edges;

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 + 2];

vector<int> re;

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;
    }

    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;
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 i = 0; i < N; i++) mem[i][id] = t[leader(i)];
        }

    }

    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 79 ms 200652 KB Output is correct
2 Correct 78 ms 200624 KB Output is correct
3 Correct 77 ms 200612 KB Output is correct
4 Correct 82 ms 200780 KB Output is correct
5 Correct 77 ms 200644 KB Output is correct
6 Correct 77 ms 200716 KB Output is correct
7 Correct 79 ms 200728 KB Output is correct
8 Correct 78 ms 200700 KB Output is correct
9 Correct 256 ms 204164 KB Output is correct
10 Correct 338 ms 204532 KB Output is correct
11 Correct 341 ms 204564 KB Output is correct
12 Correct 361 ms 204740 KB Output is correct
13 Correct 347 ms 204740 KB Output is correct
14 Correct 256 ms 204348 KB Output is correct
15 Correct 484 ms 206176 KB Output is correct
16 Correct 450 ms 206064 KB Output is correct
17 Correct 527 ms 206272 KB Output is correct
18 Correct 503 ms 206280 KB Output is correct
19 Execution timed out 2077 ms 203348 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 200652 KB Output is correct
2 Correct 78 ms 200624 KB Output is correct
3 Execution timed out 2071 ms 206020 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 200652 KB Output is correct
2 Correct 78 ms 200624 KB Output is correct
3 Correct 77 ms 200612 KB Output is correct
4 Correct 82 ms 200780 KB Output is correct
5 Correct 77 ms 200644 KB Output is correct
6 Correct 77 ms 200716 KB Output is correct
7 Correct 79 ms 200728 KB Output is correct
8 Correct 78 ms 200700 KB Output is correct
9 Correct 79 ms 200660 KB Output is correct
10 Incorrect 77 ms 200636 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 200660 KB Output is correct
2 Correct 79 ms 200652 KB Output is correct
3 Correct 78 ms 200624 KB Output is correct
4 Correct 77 ms 200612 KB Output is correct
5 Correct 82 ms 200780 KB Output is correct
6 Correct 77 ms 200644 KB Output is correct
7 Correct 77 ms 200716 KB Output is correct
8 Correct 79 ms 200728 KB Output is correct
9 Correct 78 ms 200700 KB Output is correct
10 Correct 256 ms 204164 KB Output is correct
11 Correct 338 ms 204532 KB Output is correct
12 Correct 341 ms 204564 KB Output is correct
13 Correct 361 ms 204740 KB Output is correct
14 Correct 347 ms 204740 KB Output is correct
15 Incorrect 77 ms 200636 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 200652 KB Output is correct
2 Correct 78 ms 200624 KB Output is correct
3 Correct 77 ms 200612 KB Output is correct
4 Correct 82 ms 200780 KB Output is correct
5 Correct 77 ms 200644 KB Output is correct
6 Correct 77 ms 200716 KB Output is correct
7 Correct 79 ms 200728 KB Output is correct
8 Correct 78 ms 200700 KB Output is correct
9 Correct 256 ms 204164 KB Output is correct
10 Correct 338 ms 204532 KB Output is correct
11 Correct 341 ms 204564 KB Output is correct
12 Correct 361 ms 204740 KB Output is correct
13 Correct 347 ms 204740 KB Output is correct
14 Correct 256 ms 204348 KB Output is correct
15 Correct 484 ms 206176 KB Output is correct
16 Correct 450 ms 206064 KB Output is correct
17 Correct 527 ms 206272 KB Output is correct
18 Correct 503 ms 206280 KB Output is correct
19 Execution timed out 2071 ms 206020 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 200660 KB Output is correct
2 Correct 79 ms 200652 KB Output is correct
3 Correct 78 ms 200624 KB Output is correct
4 Correct 77 ms 200612 KB Output is correct
5 Correct 82 ms 200780 KB Output is correct
6 Correct 77 ms 200644 KB Output is correct
7 Correct 77 ms 200716 KB Output is correct
8 Correct 79 ms 200728 KB Output is correct
9 Correct 78 ms 200700 KB Output is correct
10 Correct 256 ms 204164 KB Output is correct
11 Correct 338 ms 204532 KB Output is correct
12 Correct 341 ms 204564 KB Output is correct
13 Correct 361 ms 204740 KB Output is correct
14 Correct 347 ms 204740 KB Output is correct
15 Correct 256 ms 204348 KB Output is correct
16 Correct 484 ms 206176 KB Output is correct
17 Correct 450 ms 206064 KB Output is correct
18 Correct 527 ms 206272 KB Output is correct
19 Correct 503 ms 206280 KB Output is correct
20 Execution timed out 2071 ms 206020 KB Time limit exceeded
21 Halted 0 ms 0 KB -