oj.uz

Submission #522571

# Submission time Handle Problem Language Result Execution time Memory
522571 2022-02-05T07:23:57 Z Cyanmond Swapping Cities (APIO20_swap) C++17
100 / 100
 671 ms 43760 KB 
#line 1 "paper.cpp"
#include <bits/stdc++.h>

#line 3 "library2/utility/int_alias.hpp"

using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
#line 3 "library2/utility/len.hpp"

template <class Container> int len(const Container&c){
    return static_cast<int>(std::size(c));
}
#line 6 "library2/utility/priority_sort.hpp"

namespace magic {
template <class T, class... Tail>
void priority_sort_renumber(const std::vector<int> &order, std::vector<T> &head, Tail &...tail) {
    const int n = len(order);
    std::vector<T> sorted_head(n);
    for (int i = 0; i < n; ++i) {
        sorted_head[i] = head[order[i]];
    }
    head = std::move(sorted_head);
    if constexpr (sizeof...(Tail) != 0) {
        priority_sort_renumber(order, tail...);
    }
}
} // namespace magic

template <class Head, class... Tail>
std::vector<int> priority_sort(std::vector<Head> &head, std::vector<Tail> &...tail) {
    const int n = len(head);

    std::vector<std::tuple<Head, Tail..., int>> res(n);
    for (int i = 0; i < n; ++i) {
        res[i] = std::make_tuple(head[i], tail[i]..., i);
    }
    std::sort(res.begin(), res.end());

    std::vector<int> order(n);
    for (int i = 0; i < n; ++i) {
        order[i] = std::get<std::tuple_size_v<std::tuple<Head, Tail...>>>(res[i]);
    }
    magic::priority_sort_renumber(order, head, tail...);
    return order;
}
#line 3 "library2/utility/rep.hpp"

class Range {
    struct Iterator {
        int itr;
        constexpr Iterator(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept {
            ++itr;
        }
        constexpr bool operator!=(const Iterator &other) const noexcept {
            return itr != other.itr;
        }
        constexpr int operator*() const noexcept {
            return itr;
        }
    };
    const Iterator first, last;

  public:
    explicit constexpr Range(const int f, const int l) noexcept
        : first(f), last(std::max(f, l)) {}
    constexpr Iterator begin() const noexcept {
        return first;
    }
    constexpr Iterator end() const noexcept {
        return last;
    }
};

constexpr Range rep(const int l, const int r) noexcept {
    return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
    return Range(0, n);
}
#line 6 "paper.cpp"

class BubunEizokuUnionFindKaizou {
    int n;
    struct Node {
        int parent;
        int size;
        int deg1;
        int deg2;
        int deg3;
        bool cycle;
    };

    std::vector<Node> now_data;
    std::vector<i64> last_time;
    std::vector<std::vector<std::pair<i64, Node>>> history;
    std::vector<int> degree;
    std::vector<std::vector<std::pair<i64, int>>> deg_history;

  public:
    BubunEizokuUnionFindKaizou() = default;
    BubunEizokuUnionFindKaizou(const int n_) : n(n_) {
        now_data.resize(n);
        history.resize(n);
        for (const int i : rep(n)) {
            now_data[i] = {i, 1, 0, 0};
            history[i].push_back({0, {i, 1, 0, 0, 0, false}});
        }
        degree.assign(n, 0);
        last_time.assign(n, -1);
        deg_history.resize(n);
        for (const int i : rep(n)) {
            deg_history[i].push_back({0, 0});
        }
    }

    bool same(int a, int b, i64 t) {
        return root(a, t) == root(b, t);
    }

    int root(int v, i64 t) {
        if (last_time[v] == -1 or t < last_time[v]) {
            return v;
        } else {
            return root(now_data[v].parent, t);
        }
    }

    void unite(int a, int b, i64 c) {
        int ra = root(a, c), rb = root(b, c);
        if (ra == rb) {
            now_data[ra].cycle = true;
            if (degree[a] <= 3) {
                if (degree[a] == 0) {
                    ++now_data[ra].deg1;
                }
                if (degree[a] == 1) {
                    --now_data[ra].deg1;
                    ++now_data[ra].deg2;
                }
                if (degree[a] == 2) {
                    --now_data[ra].deg2;
                    ++now_data[ra].deg3;
                }
                if (degree[a] == 3) {
                    --now_data[ra].deg3;
                }
            }
            if (degree[b] <= 3) {
                if (degree[b] == 0) {
                    ++now_data[ra].deg1;
                }
                if (degree[b] == 1) {
                    --now_data[ra].deg1;
                    ++now_data[ra].deg2;
                }
                if (degree[b] == 2) {
                    --now_data[ra].deg2;
                    ++now_data[ra].deg3;
                }
            }
            ++degree[a];
            ++degree[b];
            history[ra].push_back({c, now_data[ra]});
        } else {
            if (now_data[ra].size < now_data[rb].size) {
                std::swap(a, b);
                std::swap(ra, rb);
            }
            now_data[ra].size += now_data[rb].size;
            now_data[rb].parent = ra;
            now_data[ra].deg1 += now_data[rb].deg1;
            now_data[ra].deg2 += now_data[rb].deg2;
            now_data[ra].deg3 += now_data[rb].deg3;
            now_data[ra].cycle |= now_data[rb].cycle;
            last_time[rb] = c;
            if (degree[a] <= 2) {
                if (degree[a] == 0) {
                    ++now_data[ra].deg1;
                }
                if (degree[a] == 1) {
                    --now_data[ra].deg1;
                    ++now_data[ra].deg2;
                }
                if (degree[a] == 2) {
                    --now_data[ra].deg2;
                    ++now_data[ra].deg3;
                }
            }
            if (degree[b] <= 2) {
                if (degree[b] == 0) {
                    ++now_data[ra].deg1;
                }
                if (degree[b] == 1) {
                    --now_data[ra].deg1;
                    ++now_data[ra].deg2;
                }
                if (degree[b] == 2) {
                    --now_data[ra].deg2;
                    ++now_data[ra].deg3;
                }
            }
            ++degree[a];
            ++degree[b];
            deg_history[a].push_back({c, degree[a]});
            deg_history[b].push_back({c, degree[b]});
            history[ra].push_back({c, now_data[ra]});
        }
    }

    int deg(int v, i64 t) {
        return (--std::upper_bound(deg_history[v].begin(), deg_history[v].end(),
                                   std::make_pair(t, 1000000001)))
            ->second;
    }

    Node view(int v, i64 t) {
        v = root(v, t);
        return (--std::upper_bound(history[v].begin(), history[v].end(), std::make_pair(t, 0),
                                   [](auto a, auto b) { return a.first < b.first; }))
            ->second;
    }
};

int N, M;
std::vector<int> U, V, W;
BubunEizokuUnionFindKaizou uft;

void init(int n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> w) {
    N = n;
    M = m;
    U = u;
    V = v;
    W = w;
    uft = BubunEizokuUnionFindKaizou(N);
    priority_sort(W, U, V);
    for (const int i : rep(M)) {
        uft.unite(U[i], V[i], W[i]);
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    if (not uft.same(X, Y, 1000000001)) {
        return -1;
    }
    const auto bestnode = uft.view(X, 1000000001);
    if ((not bestnode.cycle) and (bestnode.deg3 == 0)) {
        return -1;
    }
    int ok = 1000000001, ng = -1;
    while (ok - ng > 1) {
        const auto mid = (ok + ng) / 2;
        if (not uft.same(X, Y, mid)) {
            ng = mid;
        } else {
            const auto node = uft.view(X, mid);
            if ((not node.cycle) and (node.deg3 == 0)) {
                ng = mid;
            } else {
                ok = mid;
            }
        }
    }
    return ok;
}

/*
int main() {
    int N, M;
    assert(2 == scanf("%d %d", &N, &M));

    std::vector<int> U(M), V(M), W(M);
    for (int i = 0; i < M; ++i) {
        assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
    }

    int Q;
    assert(1 == scanf("%d", &Q));

    std::vector<int> X(Q), Y(Q);
    for (int i = 0; i < Q; ++i) {
        assert(2 == scanf("%d %d", &X[i], &Y[i]));
    }

    init(N, M, U, V, W);

    std::vector<int> minimum_fuel_capacities(Q);
    for (int i = 0; i < Q; ++i) {
        minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
    }

    for (int i = 0; i < Q; ++i) {
        printf("%d\n", minimum_fuel_capacities[i]);
    }

    return 0;
}
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 560 KB Output is correct
9 Correct 111 ms 24736 KB Output is correct
10 Correct 143 ms 30060 KB Output is correct
11 Correct 138 ms 29536 KB Output is correct
12 Correct 150 ms 31240 KB Output is correct
13 Correct 100 ms 29560 KB Output is correct
14 Correct 124 ms 24744 KB Output is correct
15 Correct 223 ms 32248 KB Output is correct
16 Correct 210 ms 31280 KB Output is correct
17 Correct 237 ms 33016 KB Output is correct
18 Correct 164 ms 31440 KB Output is correct
19 Correct 220 ms 9056 KB Output is correct
20 Correct 451 ms 33324 KB Output is correct
21 Correct 422 ms 32416 KB Output is correct
22 Correct 438 ms 34372 KB Output is correct
23 Correct 341 ms 32844 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 393 ms 30068 KB Output is correct
4 Correct 379 ms 31340 KB Output is correct
5 Correct 398 ms 30604 KB Output is correct
6 Correct 387 ms 31220 KB Output is correct
7 Correct 399 ms 31188 KB Output is correct
8 Correct 379 ms 30008 KB Output is correct
9 Correct 382 ms 30832 KB Output is correct
10 Correct 427 ms 29892 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 560 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 556 KB Output is correct
11 Correct 2 ms 560 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 556 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 576 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 1 ms 556 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 2 ms 428 KB Output is correct
20 Correct 1 ms 540 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Correct 1 ms 420 KB Output is correct
23 Correct 1 ms 420 KB Output is correct
24 Correct 2 ms 716 KB Output is correct
25 Correct 2 ms 684 KB Output is correct
26 Correct 2 ms 684 KB Output is correct
27 Correct 1 ms 588 KB Output is correct
28 Correct 2 ms 684 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 560 KB Output is correct
10 Correct 111 ms 24736 KB Output is correct
11 Correct 143 ms 30060 KB Output is correct
12 Correct 138 ms 29536 KB Output is correct
13 Correct 150 ms 31240 KB Output is correct
14 Correct 100 ms 29560 KB Output is correct
15 Correct 1 ms 556 KB Output is correct
16 Correct 2 ms 560 KB Output is correct
17 Correct 2 ms 588 KB Output is correct
18 Correct 2 ms 556 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 576 KB Output is correct
21 Correct 2 ms 588 KB Output is correct
22 Correct 1 ms 556 KB Output is correct
23 Correct 1 ms 588 KB Output is correct
24 Correct 2 ms 428 KB Output is correct
25 Correct 1 ms 540 KB Output is correct
26 Correct 1 ms 588 KB Output is correct
27 Correct 1 ms 420 KB Output is correct
28 Correct 1 ms 420 KB Output is correct
29 Correct 2 ms 716 KB Output is correct
30 Correct 2 ms 684 KB Output is correct
31 Correct 2 ms 684 KB Output is correct
32 Correct 1 ms 588 KB Output is correct
33 Correct 2 ms 684 KB Output is correct
34 Correct 19 ms 4436 KB Output is correct
35 Correct 156 ms 31252 KB Output is correct
36 Correct 148 ms 31184 KB Output is correct
37 Correct 154 ms 31116 KB Output is correct
38 Correct 146 ms 30768 KB Output is correct
39 Correct 140 ms 30420 KB Output is correct
40 Correct 126 ms 27484 KB Output is correct
41 Correct 172 ms 31216 KB Output is correct
42 Correct 153 ms 31368 KB Output is correct
43 Correct 99 ms 31084 KB Output is correct
44 Correct 139 ms 29832 KB Output is correct
45 Correct 137 ms 30800 KB Output is correct
46 Correct 143 ms 31340 KB Output is correct
47 Correct 143 ms 31340 KB Output is correct
48 Correct 141 ms 31352 KB Output is correct
49 Correct 71 ms 19104 KB Output is correct
50 Correct 58 ms 12892 KB Output is correct
51 Correct 113 ms 26116 KB Output is correct
52 Correct 207 ms 37512 KB Output is correct
53 Correct 181 ms 36992 KB Output is correct
54 Correct 207 ms 42188 KB Output is correct
55 Correct 112 ms 29448 KB Output is correct
56 Correct 180 ms 36844 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 560 KB Output is correct
9 Correct 111 ms 24736 KB Output is correct
10 Correct 143 ms 30060 KB Output is correct
11 Correct 138 ms 29536 KB Output is correct
12 Correct 150 ms 31240 KB Output is correct
13 Correct 100 ms 29560 KB Output is correct
14 Correct 124 ms 24744 KB Output is correct
15 Correct 223 ms 32248 KB Output is correct
16 Correct 210 ms 31280 KB Output is correct
17 Correct 237 ms 33016 KB Output is correct
18 Correct 164 ms 31440 KB Output is correct
19 Correct 393 ms 30068 KB Output is correct
20 Correct 379 ms 31340 KB Output is correct
21 Correct 398 ms 30604 KB Output is correct
22 Correct 387 ms 31220 KB Output is correct
23 Correct 399 ms 31188 KB Output is correct
24 Correct 379 ms 30008 KB Output is correct
25 Correct 382 ms 30832 KB Output is correct
26 Correct 427 ms 29892 KB Output is correct
27 Correct 1 ms 556 KB Output is correct
28 Correct 2 ms 560 KB Output is correct
29 Correct 2 ms 588 KB Output is correct
30 Correct 2 ms 556 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 1 ms 576 KB Output is correct
33 Correct 2 ms 588 KB Output is correct
34 Correct 1 ms 556 KB Output is correct
35 Correct 1 ms 588 KB Output is correct
36 Correct 19 ms 4436 KB Output is correct
37 Correct 156 ms 31252 KB Output is correct
38 Correct 148 ms 31184 KB Output is correct
39 Correct 154 ms 31116 KB Output is correct
40 Correct 146 ms 30768 KB Output is correct
41 Correct 140 ms 30420 KB Output is correct
42 Correct 126 ms 27484 KB Output is correct
43 Correct 172 ms 31216 KB Output is correct
44 Correct 153 ms 31368 KB Output is correct
45 Correct 99 ms 31084 KB Output is correct
46 Correct 139 ms 29832 KB Output is correct
47 Correct 35 ms 4592 KB Output is correct
48 Correct 472 ms 34040 KB Output is correct
49 Correct 471 ms 34120 KB Output is correct
50 Correct 474 ms 34008 KB Output is correct
51 Correct 462 ms 33868 KB Output is correct
52 Correct 442 ms 31992 KB Output is correct
53 Correct 373 ms 23676 KB Output is correct
54 Correct 471 ms 34688 KB Output is correct
55 Correct 475 ms 34056 KB Output is correct
56 Correct 376 ms 32440 KB Output is correct
57 Correct 458 ms 33068 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 560 KB Output is correct
10 Correct 111 ms 24736 KB Output is correct
11 Correct 143 ms 30060 KB Output is correct
12 Correct 138 ms 29536 KB Output is correct
13 Correct 150 ms 31240 KB Output is correct
14 Correct 100 ms 29560 KB Output is correct
15 Correct 124 ms 24744 KB Output is correct
16 Correct 223 ms 32248 KB Output is correct
17 Correct 210 ms 31280 KB Output is correct
18 Correct 237 ms 33016 KB Output is correct
19 Correct 164 ms 31440 KB Output is correct
20 Correct 393 ms 30068 KB Output is correct
21 Correct 379 ms 31340 KB Output is correct
22 Correct 398 ms 30604 KB Output is correct
23 Correct 387 ms 31220 KB Output is correct
24 Correct 399 ms 31188 KB Output is correct
25 Correct 379 ms 30008 KB Output is correct
26 Correct 382 ms 30832 KB Output is correct
27 Correct 427 ms 29892 KB Output is correct
28 Correct 1 ms 556 KB Output is correct
29 Correct 2 ms 560 KB Output is correct
30 Correct 2 ms 588 KB Output is correct
31 Correct 2 ms 556 KB Output is correct
32 Correct 1 ms 460 KB Output is correct
33 Correct 1 ms 576 KB Output is correct
34 Correct 2 ms 588 KB Output is correct
35 Correct 1 ms 556 KB Output is correct
36 Correct 1 ms 588 KB Output is correct
37 Correct 19 ms 4436 KB Output is correct
38 Correct 156 ms 31252 KB Output is correct
39 Correct 148 ms 31184 KB Output is correct
40 Correct 154 ms 31116 KB Output is correct
41 Correct 146 ms 30768 KB Output is correct
42 Correct 140 ms 30420 KB Output is correct
43 Correct 126 ms 27484 KB Output is correct
44 Correct 172 ms 31216 KB Output is correct
45 Correct 153 ms 31368 KB Output is correct
46 Correct 99 ms 31084 KB Output is correct
47 Correct 139 ms 29832 KB Output is correct
48 Correct 35 ms 4592 KB Output is correct
49 Correct 472 ms 34040 KB Output is correct
50 Correct 471 ms 34120 KB Output is correct
51 Correct 474 ms 34008 KB Output is correct
52 Correct 462 ms 33868 KB Output is correct
53 Correct 442 ms 31992 KB Output is correct
54 Correct 373 ms 23676 KB Output is correct
55 Correct 471 ms 34688 KB Output is correct
56 Correct 475 ms 34056 KB Output is correct
57 Correct 376 ms 32440 KB Output is correct
58 Correct 458 ms 33068 KB Output is correct
59 Correct 220 ms 9056 KB Output is correct
60 Correct 451 ms 33324 KB Output is correct
61 Correct 422 ms 32416 KB Output is correct
62 Correct 438 ms 34372 KB Output is correct
63 Correct 341 ms 32844 KB Output is correct
64 Correct 2 ms 428 KB Output is correct
65 Correct 1 ms 540 KB Output is correct
66 Correct 1 ms 588 KB Output is correct
67 Correct 1 ms 420 KB Output is correct
68 Correct 1 ms 420 KB Output is correct
69 Correct 2 ms 716 KB Output is correct
70 Correct 2 ms 684 KB Output is correct
71 Correct 2 ms 684 KB Output is correct
72 Correct 1 ms 588 KB Output is correct
73 Correct 2 ms 684 KB Output is correct
74 Correct 137 ms 30800 KB Output is correct
75 Correct 143 ms 31340 KB Output is correct
76 Correct 143 ms 31340 KB Output is correct
77 Correct 141 ms 31352 KB Output is correct
78 Correct 71 ms 19104 KB Output is correct
79 Correct 58 ms 12892 KB Output is correct
80 Correct 113 ms 26116 KB Output is correct
81 Correct 207 ms 37512 KB Output is correct
82 Correct 181 ms 36992 KB Output is correct
83 Correct 207 ms 42188 KB Output is correct
84 Correct 112 ms 29448 KB Output is correct
85 Correct 180 ms 36844 KB Output is correct
86 Correct 131 ms 12196 KB Output is correct
87 Correct 468 ms 34032 KB Output is correct
88 Correct 496 ms 33968 KB Output is correct
89 Correct 512 ms 31276 KB Output is correct
90 Correct 392 ms 21192 KB Output is correct
91 Correct 425 ms 22748 KB Output is correct
92 Correct 491 ms 27616 KB Output is correct
93 Correct 606 ms 39180 KB Output is correct
94 Correct 562 ms 38944 KB Output is correct
95 Correct 671 ms 43760 KB Output is correct
96 Correct 445 ms 32244 KB Output is correct
97 Correct 596 ms 35420 KB Output is correct