oj.uz

Submission #714955

# Submission time Handle Problem Language Result Execution time Memory
714955 2023-03-25T15:03:49 Z dxz05 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 361260 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

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 (rng() & 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 158 ms 355688 KB Output is correct
2 Correct 170 ms 355620 KB Output is correct
3 Correct 179 ms 355680 KB Output is correct
4 Correct 163 ms 355660 KB Output is correct
5 Correct 172 ms 355728 KB Output is correct
6 Correct 173 ms 355684 KB Output is correct
7 Correct 163 ms 355716 KB Output is correct
8 Correct 177 ms 355660 KB Output is correct
9 Correct 331 ms 359184 KB Output is correct
10 Correct 478 ms 359592 KB Output is correct
11 Correct 458 ms 359616 KB Output is correct
12 Correct 484 ms 359692 KB Output is correct
13 Correct 506 ms 359644 KB Output is correct
14 Correct 340 ms 359368 KB Output is correct
15 Correct 629 ms 361192 KB Output is correct
16 Correct 593 ms 361056 KB Output is correct
17 Correct 667 ms 361260 KB Output is correct
18 Correct 731 ms 361240 KB Output is correct
19 Execution timed out 2076 ms 358232 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 355688 KB Output is correct
2 Correct 170 ms 355620 KB Output is correct
3 Execution timed out 2082 ms 361012 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 355688 KB Output is correct
2 Correct 170 ms 355620 KB Output is correct
3 Correct 179 ms 355680 KB Output is correct
4 Correct 163 ms 355660 KB Output is correct
5 Correct 172 ms 355728 KB Output is correct
6 Correct 173 ms 355684 KB Output is correct
7 Correct 163 ms 355716 KB Output is correct
8 Correct 177 ms 355660 KB Output is correct
9 Correct 182 ms 355644 KB Output is correct
10 Incorrect 173 ms 355668 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 355644 KB Output is correct
2 Correct 158 ms 355688 KB Output is correct
3 Correct 170 ms 355620 KB Output is correct
4 Correct 179 ms 355680 KB Output is correct
5 Correct 163 ms 355660 KB Output is correct
6 Correct 172 ms 355728 KB Output is correct
7 Correct 173 ms 355684 KB Output is correct
8 Correct 163 ms 355716 KB Output is correct
9 Correct 177 ms 355660 KB Output is correct
10 Correct 331 ms 359184 KB Output is correct
11 Correct 478 ms 359592 KB Output is correct
12 Correct 458 ms 359616 KB Output is correct
13 Correct 484 ms 359692 KB Output is correct
14 Correct 506 ms 359644 KB Output is correct
15 Incorrect 173 ms 355668 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 355688 KB Output is correct
2 Correct 170 ms 355620 KB Output is correct
3 Correct 179 ms 355680 KB Output is correct
4 Correct 163 ms 355660 KB Output is correct
5 Correct 172 ms 355728 KB Output is correct
6 Correct 173 ms 355684 KB Output is correct
7 Correct 163 ms 355716 KB Output is correct
8 Correct 177 ms 355660 KB Output is correct
9 Correct 331 ms 359184 KB Output is correct
10 Correct 478 ms 359592 KB Output is correct
11 Correct 458 ms 359616 KB Output is correct
12 Correct 484 ms 359692 KB Output is correct
13 Correct 506 ms 359644 KB Output is correct
14 Correct 340 ms 359368 KB Output is correct
15 Correct 629 ms 361192 KB Output is correct
16 Correct 593 ms 361056 KB Output is correct
17 Correct 667 ms 361260 KB Output is correct
18 Correct 731 ms 361240 KB Output is correct
19 Execution timed out 2082 ms 361012 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 355644 KB Output is correct
2 Correct 158 ms 355688 KB Output is correct
3 Correct 170 ms 355620 KB Output is correct
4 Correct 179 ms 355680 KB Output is correct
5 Correct 163 ms 355660 KB Output is correct
6 Correct 172 ms 355728 KB Output is correct
7 Correct 173 ms 355684 KB Output is correct
8 Correct 163 ms 355716 KB Output is correct
9 Correct 177 ms 355660 KB Output is correct
10 Correct 331 ms 359184 KB Output is correct
11 Correct 478 ms 359592 KB Output is correct
12 Correct 458 ms 359616 KB Output is correct
13 Correct 484 ms 359692 KB Output is correct
14 Correct 506 ms 359644 KB Output is correct
15 Correct 340 ms 359368 KB Output is correct
16 Correct 629 ms 361192 KB Output is correct
17 Correct 593 ms 361056 KB Output is correct
18 Correct 667 ms 361260 KB Output is correct
19 Correct 731 ms 361240 KB Output is correct
20 Execution timed out 2082 ms 361012 KB Time limit exceeded
21 Halted 0 ms 0 KB -