oj.uz

Submission #714983

# Submission time Handle Problem Language Result Execution time Memory
714983 2023-03-25T15:58:34 Z dxz05 Swapping Cities (APIO20_swap) C++17
43 / 100
 745 ms 382324 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 *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 184 ms 374388 KB Output is correct
2 Correct 167 ms 374384 KB Output is correct
3 Correct 169 ms 374476 KB Output is correct
4 Correct 176 ms 374460 KB Output is correct
5 Correct 170 ms 374600 KB Output is correct
6 Correct 166 ms 374500 KB Output is correct
7 Correct 162 ms 374476 KB Output is correct
8 Correct 190 ms 374524 KB Output is correct
9 Correct 325 ms 378064 KB Output is correct
10 Correct 484 ms 378720 KB Output is correct
11 Correct 385 ms 378632 KB Output is correct
12 Correct 440 ms 378852 KB Output is correct
13 Correct 436 ms 378800 KB Output is correct
14 Correct 334 ms 378012 KB Output is correct
15 Correct 476 ms 380240 KB Output is correct
16 Correct 447 ms 380112 KB Output is correct
17 Correct 458 ms 380400 KB Output is correct
18 Correct 492 ms 380460 KB Output is correct
19 Correct 220 ms 378564 KB Output is correct
20 Correct 557 ms 381368 KB Output is correct
21 Correct 484 ms 381888 KB Output is correct
22 Correct 505 ms 382012 KB Output is correct
23 Correct 479 ms 382140 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 374388 KB Output is correct
2 Correct 167 ms 374384 KB Output is correct
3 Incorrect 494 ms 380284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 374388 KB Output is correct
2 Correct 167 ms 374384 KB Output is correct
3 Correct 169 ms 374476 KB Output is correct
4 Correct 176 ms 374460 KB Output is correct
5 Correct 170 ms 374600 KB Output is correct
6 Correct 166 ms 374500 KB Output is correct
7 Correct 162 ms 374476 KB Output is correct
8 Correct 190 ms 374524 KB Output is correct
9 Correct 169 ms 374476 KB Output is correct
10 Correct 180 ms 374436 KB Output is correct
11 Correct 173 ms 374516 KB Output is correct
12 Correct 165 ms 374524 KB Output is correct
13 Correct 169 ms 374496 KB Output is correct
14 Correct 175 ms 374568 KB Output is correct
15 Correct 174 ms 374476 KB Output is correct
16 Correct 172 ms 374448 KB Output is correct
17 Correct 185 ms 374424 KB Output is correct
18 Correct 164 ms 374464 KB Output is correct
19 Correct 174 ms 374500 KB Output is correct
20 Correct 198 ms 374508 KB Output is correct
21 Correct 206 ms 374488 KB Output is correct
22 Correct 218 ms 374500 KB Output is correct
23 Correct 200 ms 374496 KB Output is correct
24 Correct 211 ms 374556 KB Output is correct
25 Correct 236 ms 374560 KB Output is correct
26 Correct 177 ms 374524 KB Output is correct
27 Correct 166 ms 374420 KB Output is correct
28 Correct 171 ms 374520 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 374476 KB Output is correct
2 Correct 184 ms 374388 KB Output is correct
3 Correct 167 ms 374384 KB Output is correct
4 Correct 169 ms 374476 KB Output is correct
5 Correct 176 ms 374460 KB Output is correct
6 Correct 170 ms 374600 KB Output is correct
7 Correct 166 ms 374500 KB Output is correct
8 Correct 162 ms 374476 KB Output is correct
9 Correct 190 ms 374524 KB Output is correct
10 Correct 325 ms 378064 KB Output is correct
11 Correct 484 ms 378720 KB Output is correct
12 Correct 385 ms 378632 KB Output is correct
13 Correct 440 ms 378852 KB Output is correct
14 Correct 436 ms 378800 KB Output is correct
15 Correct 180 ms 374436 KB Output is correct
16 Correct 173 ms 374516 KB Output is correct
17 Correct 165 ms 374524 KB Output is correct
18 Correct 169 ms 374496 KB Output is correct
19 Correct 175 ms 374568 KB Output is correct
20 Correct 174 ms 374476 KB Output is correct
21 Correct 172 ms 374448 KB Output is correct
22 Correct 185 ms 374424 KB Output is correct
23 Correct 164 ms 374464 KB Output is correct
24 Correct 174 ms 374500 KB Output is correct
25 Correct 198 ms 374508 KB Output is correct
26 Correct 206 ms 374488 KB Output is correct
27 Correct 218 ms 374500 KB Output is correct
28 Correct 200 ms 374496 KB Output is correct
29 Correct 211 ms 374556 KB Output is correct
30 Correct 236 ms 374560 KB Output is correct
31 Correct 177 ms 374524 KB Output is correct
32 Correct 166 ms 374420 KB Output is correct
33 Correct 171 ms 374520 KB Output is correct
34 Correct 171 ms 375020 KB Output is correct
35 Correct 428 ms 378800 KB Output is correct
36 Correct 416 ms 378776 KB Output is correct
37 Correct 417 ms 378828 KB Output is correct
38 Correct 499 ms 378756 KB Output is correct
39 Correct 406 ms 378724 KB Output is correct
40 Correct 398 ms 378368 KB Output is correct
41 Correct 407 ms 378808 KB Output is correct
42 Correct 454 ms 378952 KB Output is correct
43 Correct 433 ms 378804 KB Output is correct
44 Correct 409 ms 378908 KB Output is correct
45 Correct 586 ms 380292 KB Output is correct
46 Correct 418 ms 378832 KB Output is correct
47 Correct 428 ms 378832 KB Output is correct
48 Correct 512 ms 379340 KB Output is correct
49 Correct 238 ms 379984 KB Output is correct
50 Correct 218 ms 378712 KB Output is correct
51 Correct 404 ms 379488 KB Output is correct
52 Correct 574 ms 380968 KB Output is correct
53 Correct 715 ms 381668 KB Output is correct
54 Correct 745 ms 382324 KB Output is correct
55 Correct 432 ms 378812 KB Output is correct
56 Correct 684 ms 381324 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 374388 KB Output is correct
2 Correct 167 ms 374384 KB Output is correct
3 Correct 169 ms 374476 KB Output is correct
4 Correct 176 ms 374460 KB Output is correct
5 Correct 170 ms 374600 KB Output is correct
6 Correct 166 ms 374500 KB Output is correct
7 Correct 162 ms 374476 KB Output is correct
8 Correct 190 ms 374524 KB Output is correct
9 Correct 325 ms 378064 KB Output is correct
10 Correct 484 ms 378720 KB Output is correct
11 Correct 385 ms 378632 KB Output is correct
12 Correct 440 ms 378852 KB Output is correct
13 Correct 436 ms 378800 KB Output is correct
14 Correct 334 ms 378012 KB Output is correct
15 Correct 476 ms 380240 KB Output is correct
16 Correct 447 ms 380112 KB Output is correct
17 Correct 458 ms 380400 KB Output is correct
18 Correct 492 ms 380460 KB Output is correct
19 Incorrect 494 ms 380284 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 374476 KB Output is correct
2 Correct 184 ms 374388 KB Output is correct
3 Correct 167 ms 374384 KB Output is correct
4 Correct 169 ms 374476 KB Output is correct
5 Correct 176 ms 374460 KB Output is correct
6 Correct 170 ms 374600 KB Output is correct
7 Correct 166 ms 374500 KB Output is correct
8 Correct 162 ms 374476 KB Output is correct
9 Correct 190 ms 374524 KB Output is correct
10 Correct 325 ms 378064 KB Output is correct
11 Correct 484 ms 378720 KB Output is correct
12 Correct 385 ms 378632 KB Output is correct
13 Correct 440 ms 378852 KB Output is correct
14 Correct 436 ms 378800 KB Output is correct
15 Correct 334 ms 378012 KB Output is correct
16 Correct 476 ms 380240 KB Output is correct
17 Correct 447 ms 380112 KB Output is correct
18 Correct 458 ms 380400 KB Output is correct
19 Correct 492 ms 380460 KB Output is correct
20 Incorrect 494 ms 380284 KB Output isn't correct
21 Halted 0 ms 0 KB -