oj.uz

Submission #965044

# Submission time Handle Problem Language Result Execution time Memory
965044 2024-04-18T04:15:45 Z Pannda Swapping Cities (APIO20_swap) C++17
37 / 100
 2000 ms 485184 KB 
#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> f;
    vector<int> siz;
    vector<int> deg;
    vector<bool> ok;

    DSU(int n) : f(n), siz(n, 1), deg(n, 0), ok(n, false) { iota(f.begin(), f.end(), 0); }

    int leader(int u) {
        while (u != f[u]) u = f[u] = f[f[u]];
        return u;
    }

    bool unionize(int u0, int v0) {
        int u = leader(u0);
        int v = leader(v0);
        if (u == v) {
            ok[u] = true;
            return false;
        }
        if (siz[u] > siz[v]) swap(u, v);
        siz[v] += siz[u];
        if (++deg[u0] >= 3 || ++deg[v0] >= 3) ok[v] = true;
        ok[v] = ok[v] | ok[u];
        f[u] = v;
        return true;
    }

    bool same(int u, int v) {
        return leader(u) == leader(v);
    }

    bool isOk(int u) {
        return ok[leader(u)];
    }
};

struct LiteDSU {
    vector<int> f;
    vector<int> siz;
    vector<bool> ok;

    LiteDSU(int n) : f(n), siz(n, 1), ok(n, false) { iota(f.begin(), f.end(), 0); }

    int leader(int u) {
        while (u != f[u]) u = f[u] = f[f[u]];
        return u;
    }

    bool unionize(int u, int v) {
        u = leader(u);
        v = leader(v);
        if (u == v) return false;
        if (siz[u] > siz[v]) swap(u, v);
        siz[v] += siz[u];
        ok[v] = ok[v] | ok[u];
        f[u] = v;
        return true;
    }

    bool same(int u, int v) {
        return leader(u) == leader(v);
    }

    bool isOk(int u) {
        return ok[leader(u)];
    }
};

int n, m;
vector<array<int, 3>> edges;
const int B = 500;
vector<DSU> dsus;
int b;
vector<int> mp;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    m = M;
    edges.resize(m);
    for (int i = 0; i < m; i++) {
        edges[i] = {U[i], V[i], W[i]};
    }
    sort(edges.begin(), edges.end(), [&](array<int, 3> e0, array<int, 3> e1) { return e0[2] < e1[2]; });

    dsus.emplace_back(n);
    for (b = 0; B * b < m; b++) {
        dsus.push_back(dsus.back());
        for (int i = B * b; i < min(m, B * b + B); i++) {
            dsus.back().unionize(edges[i][0], edges[i][1]);
        }
    }
    b++;

    mp.resize(n, -1);
}

int getMinimumFuelCapacity(int X, int Y) {
    if (!dsus.back().same(X, Y) || !dsus.back().isOk(X)) return -1;
    int b0 = b - 1;
    while (dsus[b0].same(X, Y) && dsus[b0].isOk(X)) b0--;
    vector<int> dom;
    for (int i = B * b0; i < min(m, B * b0 + B); i++) {
        if (dsus[b0 + 1].same(X, edges[i][0]) || dsus[b0 + 1].same(X, edges[i][1])) {
            int u = dsus[b0].leader(edges[i][0]);
            int v = dsus[b0].leader(edges[i][1]);
            if (mp[u] == -1) mp[u] = 0, dom.push_back(u);
            if (mp[v] == -1) mp[v] = 0, dom.push_back(v);
        }
    }
    int c = dom.size();
    int label = 0;
    for (int u : dom) mp[u] = label++;
    int x = mp[dsus[b0].leader(X)];
    int y = mp[dsus[b0].leader(Y)];
    LiteDSU dsu(c);
    int res = -2;
    vector<int> defer;
    for (int u : dom) if (dsus[b0].isOk(u)) dsu.ok[mp[u]] = true;
    for (int i = B * b0; i < min(m, B * b0 + B); i++) {
        if (dsus[b0 + 1].same(X, edges[i][0]) || dsus[b0 + 1].same(X, edges[i][1])) {
            int u = mp[dsus[b0].leader(edges[i][0])];
            int v = mp[dsus[b0].leader(edges[i][1])];
            if (dsu.same(u, v)) {
                dsu.ok[dsu.leader(u)] = true;
            } else {
                defer.push_back(edges[i][0]);
                defer.push_back(edges[i][1]);
                if (++dsus[b0].deg[edges[i][0]] >= 3) dsu.ok[dsu.leader(u)] = true;
                if (++dsus[b0].deg[edges[i][1]] >= 3) dsu.ok[dsu.leader(v)] = true;
                dsu.unionize(u, v);
            }
            if (dsu.same(x, y) && dsu.isOk(x)) {
                res = edges[i][2];
                break;
            }
        }
    }
    for (int u : defer) dsus[b0].deg[u]--;
    for (int u : dom) mp[u] = -1;
    return res;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 79 ms 151124 KB Output is correct
10 Correct 128 ms 225696 KB Output is correct
11 Correct 128 ms 218648 KB Output is correct
12 Correct 119 ms 243528 KB Output is correct
13 Correct 114 ms 243444 KB Output is correct
14 Correct 89 ms 151464 KB Output is correct
15 Correct 166 ms 230876 KB Output is correct
16 Correct 153 ms 218272 KB Output is correct
17 Correct 155 ms 245364 KB Output is correct
18 Correct 158 ms 245436 KB Output is correct
19 Execution timed out 2063 ms 9048 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2045 ms 221396 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 2 ms 348 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 79 ms 151124 KB Output is correct
11 Correct 128 ms 225696 KB Output is correct
12 Correct 128 ms 218648 KB Output is correct
13 Correct 119 ms 243528 KB Output is correct
14 Correct 114 ms 243444 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 2 ms 348 KB Output is correct
34 Correct 6 ms 5468 KB Output is correct
35 Correct 118 ms 243536 KB Output is correct
36 Correct 119 ms 243536 KB Output is correct
37 Correct 114 ms 243532 KB Output is correct
38 Correct 115 ms 238664 KB Output is correct
39 Correct 122 ms 235324 KB Output is correct
40 Correct 104 ms 197400 KB Output is correct
41 Correct 118 ms 243532 KB Output is correct
42 Correct 116 ms 243628 KB Output is correct
43 Correct 120 ms 243584 KB Output is correct
44 Correct 122 ms 243464 KB Output is correct
45 Correct 151 ms 281720 KB Output is correct
46 Correct 115 ms 243536 KB Output is correct
47 Correct 114 ms 244816 KB Output is correct
48 Correct 126 ms 262024 KB Output is correct
49 Correct 52 ms 9964 KB Output is correct
50 Correct 44 ms 25936 KB Output is correct
51 Correct 122 ms 202644 KB Output is correct
52 Correct 199 ms 392296 KB Output is correct
53 Correct 212 ms 434396 KB Output is correct
54 Correct 261 ms 485184 KB Output is correct
55 Correct 114 ms 244844 KB Output is correct
56 Correct 228 ms 417428 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 79 ms 151124 KB Output is correct
10 Correct 128 ms 225696 KB Output is correct
11 Correct 128 ms 218648 KB Output is correct
12 Correct 119 ms 243528 KB Output is correct
13 Correct 114 ms 243444 KB Output is correct
14 Correct 89 ms 151464 KB Output is correct
15 Correct 166 ms 230876 KB Output is correct
16 Correct 153 ms 218272 KB Output is correct
17 Correct 155 ms 245364 KB Output is correct
18 Correct 158 ms 245436 KB Output is correct
19 Execution timed out 2045 ms 221396 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 79 ms 151124 KB Output is correct
11 Correct 128 ms 225696 KB Output is correct
12 Correct 128 ms 218648 KB Output is correct
13 Correct 119 ms 243528 KB Output is correct
14 Correct 114 ms 243444 KB Output is correct
15 Correct 89 ms 151464 KB Output is correct
16 Correct 166 ms 230876 KB Output is correct
17 Correct 153 ms 218272 KB Output is correct
18 Correct 155 ms 245364 KB Output is correct
19 Correct 158 ms 245436 KB Output is correct
20 Execution timed out 2045 ms 221396 KB Time limit exceeded
21 Halted 0 ms 0 KB -