oj.uz

Submission #714939

# Submission time Handle Problem Language Result Execution time Memory
714939 2023-03-25T14:29:04 Z dxz05 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 206300 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 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 77 ms 200604 KB Output is correct
2 Correct 79 ms 200600 KB Output is correct
3 Correct 82 ms 200744 KB Output is correct
4 Correct 87 ms 200648 KB Output is correct
5 Correct 78 ms 200656 KB Output is correct
6 Correct 79 ms 200652 KB Output is correct
7 Correct 80 ms 200652 KB Output is correct
8 Correct 80 ms 200688 KB Output is correct
9 Correct 246 ms 204176 KB Output is correct
10 Correct 353 ms 204668 KB Output is correct
11 Correct 337 ms 204664 KB Output is correct
12 Correct 375 ms 204612 KB Output is correct
13 Correct 390 ms 204672 KB Output is correct
14 Correct 245 ms 204292 KB Output is correct
15 Correct 487 ms 206156 KB Output is correct
16 Correct 468 ms 206116 KB Output is correct
17 Correct 509 ms 206300 KB Output is correct
18 Correct 512 ms 206276 KB Output is correct
19 Execution timed out 2094 ms 203180 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 200604 KB Output is correct
2 Correct 79 ms 200600 KB Output is correct
3 Execution timed out 2051 ms 205988 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 200604 KB Output is correct
2 Correct 79 ms 200600 KB Output is correct
3 Correct 82 ms 200744 KB Output is correct
4 Correct 87 ms 200648 KB Output is correct
5 Correct 78 ms 200656 KB Output is correct
6 Correct 79 ms 200652 KB Output is correct
7 Correct 80 ms 200652 KB Output is correct
8 Correct 80 ms 200688 KB Output is correct
9 Correct 78 ms 200656 KB Output is correct
10 Incorrect 81 ms 200792 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 200656 KB Output is correct
2 Correct 77 ms 200604 KB Output is correct
3 Correct 79 ms 200600 KB Output is correct
4 Correct 82 ms 200744 KB Output is correct
5 Correct 87 ms 200648 KB Output is correct
6 Correct 78 ms 200656 KB Output is correct
7 Correct 79 ms 200652 KB Output is correct
8 Correct 80 ms 200652 KB Output is correct
9 Correct 80 ms 200688 KB Output is correct
10 Correct 246 ms 204176 KB Output is correct
11 Correct 353 ms 204668 KB Output is correct
12 Correct 337 ms 204664 KB Output is correct
13 Correct 375 ms 204612 KB Output is correct
14 Correct 390 ms 204672 KB Output is correct
15 Incorrect 81 ms 200792 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 200604 KB Output is correct
2 Correct 79 ms 200600 KB Output is correct
3 Correct 82 ms 200744 KB Output is correct
4 Correct 87 ms 200648 KB Output is correct
5 Correct 78 ms 200656 KB Output is correct
6 Correct 79 ms 200652 KB Output is correct
7 Correct 80 ms 200652 KB Output is correct
8 Correct 80 ms 200688 KB Output is correct
9 Correct 246 ms 204176 KB Output is correct
10 Correct 353 ms 204668 KB Output is correct
11 Correct 337 ms 204664 KB Output is correct
12 Correct 375 ms 204612 KB Output is correct
13 Correct 390 ms 204672 KB Output is correct
14 Correct 245 ms 204292 KB Output is correct
15 Correct 487 ms 206156 KB Output is correct
16 Correct 468 ms 206116 KB Output is correct
17 Correct 509 ms 206300 KB Output is correct
18 Correct 512 ms 206276 KB Output is correct
19 Execution timed out 2051 ms 205988 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 200656 KB Output is correct
2 Correct 77 ms 200604 KB Output is correct
3 Correct 79 ms 200600 KB Output is correct
4 Correct 82 ms 200744 KB Output is correct
5 Correct 87 ms 200648 KB Output is correct
6 Correct 78 ms 200656 KB Output is correct
7 Correct 79 ms 200652 KB Output is correct
8 Correct 80 ms 200652 KB Output is correct
9 Correct 80 ms 200688 KB Output is correct
10 Correct 246 ms 204176 KB Output is correct
11 Correct 353 ms 204668 KB Output is correct
12 Correct 337 ms 204664 KB Output is correct
13 Correct 375 ms 204612 KB Output is correct
14 Correct 390 ms 204672 KB Output is correct
15 Correct 245 ms 204292 KB Output is correct
16 Correct 487 ms 206156 KB Output is correct
17 Correct 468 ms 206116 KB Output is correct
18 Correct 509 ms 206300 KB Output is correct
19 Correct 512 ms 206276 KB Output is correct
20 Execution timed out 2051 ms 205988 KB Time limit exceeded
21 Halted 0 ms 0 KB -