oj.uz

Submission #714984

# Submission time Handle Problem Language Result Execution time Memory
714984 2023-03-25T16:00:40 Z dxz05 Swapping Cities (APIO20_swap) C++17
43 / 100
 758 ms 385580 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 = 850;

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;

bool sub1, sub2;

tuple<int, int, int> edges[MaxM];
int foo[MaxN];

void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
    N = _N, M = _M;

    vector<int> deg(N, 0);

    sub2 = true;
    for (int i = 0; i < M; i++){
        edges[i] = make_tuple(W[i], U[i], V[i]);
        if (U[i] != 0) sub2 = false;
        deg[U[i]]++;
        deg[V[i]]++;
        foo[V[i]] = W[i];
    }

    sub1 = true;
    for (int i = 0; i < N; i++){
        if (deg[i] > 2) sub1 = false;
    }

    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++){
        int u = get<1>(edges[i]), v = get<2>(edges[i]);
        unite(u, v);

        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) {
    if (sub1) return (M == N ? get<0>(edges[M - 1]) : -1);

    if (sub2){
        if (X == 0){
            return max(foo[Y], get<0>(edges[1]));
        } else {
            multiset<int> s;
            for (int i = 0; i < 3; i++) s.insert(get<0>(edges[i]));
            if (s.find(foo[X]) != s.end()) s.erase(s.find(foo[X]));
            if (s.find(foo[Y]) != s.end()) s.erase(s.find(foo[Y]));
            return max({foo[X], foo[Y], *s.begin()});
        }
    }

    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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 374480 KB Output is correct
2 Correct 169 ms 374444 KB Output is correct
3 Correct 170 ms 374568 KB Output is correct
4 Correct 169 ms 374484 KB Output is correct
5 Correct 172 ms 374416 KB Output is correct
6 Correct 176 ms 374472 KB Output is correct
7 Correct 183 ms 374428 KB Output is correct
8 Correct 186 ms 374444 KB Output is correct
9 Correct 374 ms 377912 KB Output is correct
10 Correct 627 ms 378636 KB Output is correct
11 Correct 503 ms 378672 KB Output is correct
12 Correct 408 ms 378808 KB Output is correct
13 Correct 482 ms 378928 KB Output is correct
14 Correct 317 ms 378028 KB Output is correct
15 Correct 482 ms 380240 KB Output is correct
16 Correct 436 ms 380172 KB Output is correct
17 Correct 522 ms 380400 KB Output is correct
18 Correct 529 ms 380452 KB Output is correct
19 Correct 216 ms 378536 KB Output is correct
20 Correct 506 ms 381464 KB Output is correct
21 Correct 453 ms 381472 KB Output is correct
22 Correct 487 ms 381640 KB Output is correct
23 Correct 469 ms 381748 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 374480 KB Output is correct
2 Correct 169 ms 374444 KB Output is correct
3 Correct 462 ms 381276 KB Output is correct
4 Correct 494 ms 385196 KB Output is correct
5 Incorrect 480 ms 385580 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 374480 KB Output is correct
2 Correct 169 ms 374444 KB Output is correct
3 Correct 170 ms 374568 KB Output is correct
4 Correct 169 ms 374484 KB Output is correct
5 Correct 172 ms 374416 KB Output is correct
6 Correct 176 ms 374472 KB Output is correct
7 Correct 183 ms 374428 KB Output is correct
8 Correct 186 ms 374444 KB Output is correct
9 Correct 176 ms 374408 KB Output is correct
10 Correct 202 ms 374448 KB Output is correct
11 Correct 185 ms 374436 KB Output is correct
12 Correct 173 ms 374476 KB Output is correct
13 Correct 192 ms 374476 KB Output is correct
14 Correct 171 ms 374500 KB Output is correct
15 Correct 175 ms 374424 KB Output is correct
16 Correct 195 ms 374520 KB Output is correct
17 Correct 191 ms 374476 KB Output is correct
18 Correct 176 ms 374436 KB Output is correct
19 Correct 171 ms 374600 KB Output is correct
20 Correct 180 ms 374512 KB Output is correct
21 Correct 168 ms 374508 KB Output is correct
22 Correct 169 ms 374460 KB Output is correct
23 Correct 172 ms 374524 KB Output is correct
24 Correct 182 ms 374556 KB Output is correct
25 Correct 167 ms 374496 KB Output is correct
26 Correct 174 ms 374480 KB Output is correct
27 Correct 197 ms 374580 KB Output is correct
28 Correct 180 ms 374604 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 374408 KB Output is correct
2 Correct 166 ms 374480 KB Output is correct
3 Correct 169 ms 374444 KB Output is correct
4 Correct 170 ms 374568 KB Output is correct
5 Correct 169 ms 374484 KB Output is correct
6 Correct 172 ms 374416 KB Output is correct
7 Correct 176 ms 374472 KB Output is correct
8 Correct 183 ms 374428 KB Output is correct
9 Correct 186 ms 374444 KB Output is correct
10 Correct 374 ms 377912 KB Output is correct
11 Correct 627 ms 378636 KB Output is correct
12 Correct 503 ms 378672 KB Output is correct
13 Correct 408 ms 378808 KB Output is correct
14 Correct 482 ms 378928 KB Output is correct
15 Correct 202 ms 374448 KB Output is correct
16 Correct 185 ms 374436 KB Output is correct
17 Correct 173 ms 374476 KB Output is correct
18 Correct 192 ms 374476 KB Output is correct
19 Correct 171 ms 374500 KB Output is correct
20 Correct 175 ms 374424 KB Output is correct
21 Correct 195 ms 374520 KB Output is correct
22 Correct 191 ms 374476 KB Output is correct
23 Correct 176 ms 374436 KB Output is correct
24 Correct 171 ms 374600 KB Output is correct
25 Correct 180 ms 374512 KB Output is correct
26 Correct 168 ms 374508 KB Output is correct
27 Correct 169 ms 374460 KB Output is correct
28 Correct 172 ms 374524 KB Output is correct
29 Correct 182 ms 374556 KB Output is correct
30 Correct 167 ms 374496 KB Output is correct
31 Correct 174 ms 374480 KB Output is correct
32 Correct 197 ms 374580 KB Output is correct
33 Correct 180 ms 374604 KB Output is correct
34 Correct 181 ms 375036 KB Output is correct
35 Correct 442 ms 378896 KB Output is correct
36 Correct 420 ms 378900 KB Output is correct
37 Correct 410 ms 378828 KB Output is correct
38 Correct 445 ms 378796 KB Output is correct
39 Correct 420 ms 378720 KB Output is correct
40 Correct 436 ms 378472 KB Output is correct
41 Correct 428 ms 378840 KB Output is correct
42 Correct 420 ms 378824 KB Output is correct
43 Correct 429 ms 378828 KB Output is correct
44 Correct 451 ms 378936 KB Output is correct
45 Correct 508 ms 380364 KB Output is correct
46 Correct 439 ms 378832 KB Output is correct
47 Correct 450 ms 378852 KB Output is correct
48 Correct 455 ms 379180 KB Output is correct
49 Correct 253 ms 380108 KB Output is correct
50 Correct 227 ms 378792 KB Output is correct
51 Correct 386 ms 379500 KB Output is correct
52 Correct 606 ms 380972 KB Output is correct
53 Correct 668 ms 381600 KB Output is correct
54 Correct 758 ms 382328 KB Output is correct
55 Correct 415 ms 378868 KB Output is correct
56 Correct 665 ms 381364 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 374480 KB Output is correct
2 Correct 169 ms 374444 KB Output is correct
3 Correct 170 ms 374568 KB Output is correct
4 Correct 169 ms 374484 KB Output is correct
5 Correct 172 ms 374416 KB Output is correct
6 Correct 176 ms 374472 KB Output is correct
7 Correct 183 ms 374428 KB Output is correct
8 Correct 186 ms 374444 KB Output is correct
9 Correct 374 ms 377912 KB Output is correct
10 Correct 627 ms 378636 KB Output is correct
11 Correct 503 ms 378672 KB Output is correct
12 Correct 408 ms 378808 KB Output is correct
13 Correct 482 ms 378928 KB Output is correct
14 Correct 317 ms 378028 KB Output is correct
15 Correct 482 ms 380240 KB Output is correct
16 Correct 436 ms 380172 KB Output is correct
17 Correct 522 ms 380400 KB Output is correct
18 Correct 529 ms 380452 KB Output is correct
19 Correct 462 ms 381276 KB Output is correct
20 Correct 494 ms 385196 KB Output is correct
21 Incorrect 480 ms 385580 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 374408 KB Output is correct
2 Correct 166 ms 374480 KB Output is correct
3 Correct 169 ms 374444 KB Output is correct
4 Correct 170 ms 374568 KB Output is correct
5 Correct 169 ms 374484 KB Output is correct
6 Correct 172 ms 374416 KB Output is correct
7 Correct 176 ms 374472 KB Output is correct
8 Correct 183 ms 374428 KB Output is correct
9 Correct 186 ms 374444 KB Output is correct
10 Correct 374 ms 377912 KB Output is correct
11 Correct 627 ms 378636 KB Output is correct
12 Correct 503 ms 378672 KB Output is correct
13 Correct 408 ms 378808 KB Output is correct
14 Correct 482 ms 378928 KB Output is correct
15 Correct 317 ms 378028 KB Output is correct
16 Correct 482 ms 380240 KB Output is correct
17 Correct 436 ms 380172 KB Output is correct
18 Correct 522 ms 380400 KB Output is correct
19 Correct 529 ms 380452 KB Output is correct
20 Correct 462 ms 381276 KB Output is correct
21 Correct 494 ms 385196 KB Output is correct
22 Incorrect 480 ms 385580 KB Output isn't correct
23 Halted 0 ms 0 KB -