oj.uz

Submission #714957

# Submission time Handle Problem Language Result Execution time Memory
714957 2023-03-25T15:11:41 Z dxz05 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 359496 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 = 100002;
const int MaxM = 200002;

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

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 (rng() & 1){
        swap(x, y);
        swap(X, 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[MaxM], er[MaxM];

int blockCount;

tuple<int, int, int> edges[MaxM];
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[i] = make_tuple(W[i], U[i], V[i]);
    }

    sort(edges, edges + M);

    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 157 ms 354068 KB Output is correct
2 Correct 162 ms 354032 KB Output is correct
3 Correct 162 ms 354128 KB Output is correct
4 Correct 160 ms 354116 KB Output is correct
5 Correct 157 ms 354080 KB Output is correct
6 Correct 160 ms 354224 KB Output is correct
7 Correct 175 ms 354124 KB Output is correct
8 Correct 158 ms 354100 KB Output is correct
9 Correct 301 ms 356940 KB Output is correct
10 Correct 365 ms 357620 KB Output is correct
11 Correct 394 ms 357580 KB Output is correct
12 Correct 409 ms 357832 KB Output is correct
13 Correct 403 ms 357672 KB Output is correct
14 Correct 321 ms 357088 KB Output is correct
15 Correct 524 ms 359480 KB Output is correct
16 Correct 577 ms 359296 KB Output is correct
17 Correct 530 ms 359468 KB Output is correct
18 Correct 547 ms 359496 KB Output is correct
19 Execution timed out 2072 ms 356472 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 354068 KB Output is correct
2 Correct 162 ms 354032 KB Output is correct
3 Execution timed out 2073 ms 358980 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 354068 KB Output is correct
2 Correct 162 ms 354032 KB Output is correct
3 Correct 162 ms 354128 KB Output is correct
4 Correct 160 ms 354116 KB Output is correct
5 Correct 157 ms 354080 KB Output is correct
6 Correct 160 ms 354224 KB Output is correct
7 Correct 175 ms 354124 KB Output is correct
8 Correct 158 ms 354100 KB Output is correct
9 Correct 163 ms 354168 KB Output is correct
10 Incorrect 169 ms 354140 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 354168 KB Output is correct
2 Correct 157 ms 354068 KB Output is correct
3 Correct 162 ms 354032 KB Output is correct
4 Correct 162 ms 354128 KB Output is correct
5 Correct 160 ms 354116 KB Output is correct
6 Correct 157 ms 354080 KB Output is correct
7 Correct 160 ms 354224 KB Output is correct
8 Correct 175 ms 354124 KB Output is correct
9 Correct 158 ms 354100 KB Output is correct
10 Correct 301 ms 356940 KB Output is correct
11 Correct 365 ms 357620 KB Output is correct
12 Correct 394 ms 357580 KB Output is correct
13 Correct 409 ms 357832 KB Output is correct
14 Correct 403 ms 357672 KB Output is correct
15 Incorrect 169 ms 354140 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 354068 KB Output is correct
2 Correct 162 ms 354032 KB Output is correct
3 Correct 162 ms 354128 KB Output is correct
4 Correct 160 ms 354116 KB Output is correct
5 Correct 157 ms 354080 KB Output is correct
6 Correct 160 ms 354224 KB Output is correct
7 Correct 175 ms 354124 KB Output is correct
8 Correct 158 ms 354100 KB Output is correct
9 Correct 301 ms 356940 KB Output is correct
10 Correct 365 ms 357620 KB Output is correct
11 Correct 394 ms 357580 KB Output is correct
12 Correct 409 ms 357832 KB Output is correct
13 Correct 403 ms 357672 KB Output is correct
14 Correct 321 ms 357088 KB Output is correct
15 Correct 524 ms 359480 KB Output is correct
16 Correct 577 ms 359296 KB Output is correct
17 Correct 530 ms 359468 KB Output is correct
18 Correct 547 ms 359496 KB Output is correct
19 Execution timed out 2073 ms 358980 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 354168 KB Output is correct
2 Correct 157 ms 354068 KB Output is correct
3 Correct 162 ms 354032 KB Output is correct
4 Correct 162 ms 354128 KB Output is correct
5 Correct 160 ms 354116 KB Output is correct
6 Correct 157 ms 354080 KB Output is correct
7 Correct 160 ms 354224 KB Output is correct
8 Correct 175 ms 354124 KB Output is correct
9 Correct 158 ms 354100 KB Output is correct
10 Correct 301 ms 356940 KB Output is correct
11 Correct 365 ms 357620 KB Output is correct
12 Correct 394 ms 357580 KB Output is correct
13 Correct 409 ms 357832 KB Output is correct
14 Correct 403 ms 357672 KB Output is correct
15 Correct 321 ms 357088 KB Output is correct
16 Correct 524 ms 359480 KB Output is correct
17 Correct 577 ms 359296 KB Output is correct
18 Correct 530 ms 359468 KB Output is correct
19 Correct 547 ms 359496 KB Output is correct
20 Execution timed out 2073 ms 358980 KB Time limit exceeded
21 Halted 0 ms 0 KB -