oj.uz

Submission #714953

# Submission time Handle Problem Language Result Execution time Memory
714953 2023-03-25T14:58:45 Z dxz05 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 361216 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];

int re[MaxN];
int _nxt;

int leader(int x){
    if (MAGIC != -1 && !flag[x]){
        t[x] = (MAGIC == 0 ? Set(x) : mem[x][MAGIC - 1]);
        flag[x] = true;
        re[_nxt++] = 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;

    _nxt = 0;

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

    return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 355616 KB Output is correct
2 Correct 144 ms 355604 KB Output is correct
3 Correct 156 ms 355604 KB Output is correct
4 Correct 143 ms 355632 KB Output is correct
5 Correct 136 ms 355672 KB Output is correct
6 Correct 161 ms 355628 KB Output is correct
7 Correct 146 ms 355852 KB Output is correct
8 Correct 151 ms 355640 KB Output is correct
9 Correct 313 ms 359188 KB Output is correct
10 Correct 400 ms 359580 KB Output is correct
11 Correct 369 ms 359516 KB Output is correct
12 Correct 418 ms 359688 KB Output is correct
13 Correct 389 ms 359728 KB Output is correct
14 Correct 307 ms 359272 KB Output is correct
15 Correct 495 ms 361160 KB Output is correct
16 Correct 477 ms 361060 KB Output is correct
17 Correct 540 ms 361188 KB Output is correct
18 Correct 564 ms 361216 KB Output is correct
19 Execution timed out 2083 ms 358300 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 355616 KB Output is correct
2 Correct 144 ms 355604 KB Output is correct
3 Execution timed out 2059 ms 361036 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 355616 KB Output is correct
2 Correct 144 ms 355604 KB Output is correct
3 Correct 156 ms 355604 KB Output is correct
4 Correct 143 ms 355632 KB Output is correct
5 Correct 136 ms 355672 KB Output is correct
6 Correct 161 ms 355628 KB Output is correct
7 Correct 146 ms 355852 KB Output is correct
8 Correct 151 ms 355640 KB Output is correct
9 Correct 139 ms 355660 KB Output is correct
10 Incorrect 142 ms 355688 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 355660 KB Output is correct
2 Correct 152 ms 355616 KB Output is correct
3 Correct 144 ms 355604 KB Output is correct
4 Correct 156 ms 355604 KB Output is correct
5 Correct 143 ms 355632 KB Output is correct
6 Correct 136 ms 355672 KB Output is correct
7 Correct 161 ms 355628 KB Output is correct
8 Correct 146 ms 355852 KB Output is correct
9 Correct 151 ms 355640 KB Output is correct
10 Correct 313 ms 359188 KB Output is correct
11 Correct 400 ms 359580 KB Output is correct
12 Correct 369 ms 359516 KB Output is correct
13 Correct 418 ms 359688 KB Output is correct
14 Correct 389 ms 359728 KB Output is correct
15 Incorrect 142 ms 355688 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 355616 KB Output is correct
2 Correct 144 ms 355604 KB Output is correct
3 Correct 156 ms 355604 KB Output is correct
4 Correct 143 ms 355632 KB Output is correct
5 Correct 136 ms 355672 KB Output is correct
6 Correct 161 ms 355628 KB Output is correct
7 Correct 146 ms 355852 KB Output is correct
8 Correct 151 ms 355640 KB Output is correct
9 Correct 313 ms 359188 KB Output is correct
10 Correct 400 ms 359580 KB Output is correct
11 Correct 369 ms 359516 KB Output is correct
12 Correct 418 ms 359688 KB Output is correct
13 Correct 389 ms 359728 KB Output is correct
14 Correct 307 ms 359272 KB Output is correct
15 Correct 495 ms 361160 KB Output is correct
16 Correct 477 ms 361060 KB Output is correct
17 Correct 540 ms 361188 KB Output is correct
18 Correct 564 ms 361216 KB Output is correct
19 Execution timed out 2059 ms 361036 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 355660 KB Output is correct
2 Correct 152 ms 355616 KB Output is correct
3 Correct 144 ms 355604 KB Output is correct
4 Correct 156 ms 355604 KB Output is correct
5 Correct 143 ms 355632 KB Output is correct
6 Correct 136 ms 355672 KB Output is correct
7 Correct 161 ms 355628 KB Output is correct
8 Correct 146 ms 355852 KB Output is correct
9 Correct 151 ms 355640 KB Output is correct
10 Correct 313 ms 359188 KB Output is correct
11 Correct 400 ms 359580 KB Output is correct
12 Correct 369 ms 359516 KB Output is correct
13 Correct 418 ms 359688 KB Output is correct
14 Correct 389 ms 359728 KB Output is correct
15 Correct 307 ms 359272 KB Output is correct
16 Correct 495 ms 361160 KB Output is correct
17 Correct 477 ms 361060 KB Output is correct
18 Correct 540 ms 361188 KB Output is correct
19 Correct 564 ms 361216 KB Output is correct
20 Execution timed out 2059 ms 361036 KB Time limit exceeded
21 Halted 0 ms 0 KB -