oj.uz

Submission #395959

# Submission time Handle Problem Language Result Execution time Memory
395959 2021-04-29T09:18:00 Z palilo JOI15_road_development (JOI15_road_development) C++17
100 / 100
 603 ms 23760 KB 
#include <bits/stdc++.h>
using namespace std;

namespace std {
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template <class Fun>
class y_combinator_result {
    Fun fun_;

public:
    template <class T>
    explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {}

    template <class... Args>
    decltype(auto) operator()(Args&&... args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template <class Fun>
decltype(auto) y_combinator(Fun&& fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
}; // namespace std

struct disjoint_set {
    vector<int> par;
    disjoint_set(int n) : par(n, -1) {}
    int find(int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    bool merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;

        if (par[u] > par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        return true;
    }
    void clear() {
        fill(par.begin(), par.end(), -1);
    }
};

template <typename node_t>
struct lazy_seg {
    lazy_seg(int _n) : n(_n), height(__lg(_n - 1) + 1), size(1 << height), tree(size << 1) {
        for (int i = 1, len = tree.size(); i < int(tree.size()); ++i) {
            if (!(i & (i - 1))) len >>= 1;
            tree[i] = len;
        }
    }

    node_t& operator[](int i) { return tree[size + i]; }
    void apply(int l, int r) {
        apply(l, r, 0, size, 1);
    }
    node_t prod(int l, int r) {
        return prod(l, r, 0, size, 1);
    }

private:
    const int n, height, size;
    vector<node_t> tree;

#define lson (i << 1)
#define rson (i << 1 | 1)
    void apply(int ql, int qr, int l, int r, int i) {
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr) {
            tree[i] = 0;
            return;
        }
        if (!tree[i]) push(i);

        const int m = (l + r) >> 1;
        apply(ql, qr, l, m, lson), apply(ql, qr, m, r, rson);
        pull(i);
    }
    node_t prod(int ql, int qr, int l, int r, int i) {
        if (qr <= l || r <= ql) return 0;
        if (ql <= l && r <= qr) return tree[i];
        if (!tree[i]) push(i);

        const int m = (l + r) >> 1;
        return op(prod(ql, qr, l, m, lson), prod(ql, qr, m, r, rson));
    }
    void pull(int i) {
        tree[i] = op(tree[lson], tree[rson]);
    }
    void push(int i) {
        tree[lson] = tree[rson] = 0;
    }
    node_t op(node_t lhs, node_t rhs) {
        return lhs + rhs;
    }
#undef lson
#undef rson
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef home
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int n, q;
    cin >> n >> q;

    disjoint_set dsu(n);
    vector<vector<int>> adj(n);

    vector<pair<int, int>> queries(q);
    for (auto& [u, v] : queries) {
        char type;
        cin >> type >> u >> v, --u, --v;
        if (type == '1') {
            if (dsu.merge(u, v))
                adj[u].emplace_back(v), adj[v].emplace_back(u);
        } else
            u = ~u, v = ~v;
    }

    // <hld>
    vector<int> par(n, -1), sz(n), top(n), in(n), dep(n);
    auto dfs = y_combinator([&](auto self, int u) -> void {
        sz[u] = 1;
        for (auto& v : adj[u]) {
            par[v] = u, dep[v] = dep[u] + 1;
            adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
            self(v);
            sz[u] += sz[v];
            if (sz[v] > sz[adj[u][0]])
                swap(v, adj[u][0]);
        }
    });
    auto hld = y_combinator([&](auto self, int u) -> void {
        static int t = 0;
        in[u] = t++;
        bool heavy = true;
        for (const auto& v : adj[u]) {
            top[v] = heavy ? top[u] : v;
            self(v);
            heavy = false;
        }
    });
    // </hld>

    for (int i = 0; i < n; ++i)
        if (par[i] == -1) {
            dfs(i);
            hld(i);
        }

    lazy_seg<int> seg(n);
    auto develop = [&](int u, int v) {
        for (; top[u] != top[v]; u = par[top[u]]) {
            if (sz[top[u]] > sz[top[v]]) swap(u, v);
            seg.apply(in[top[u]], in[u] + 1);
        }
        if (in[u] > in[v]) swap(u, v);
        seg.apply(in[u] + 1, in[v] + 1);
    };
    auto counting = [&](int u, int v) {
        int res = 0, len = dep[u] + dep[v];
        for (; top[u] != top[v]; u = par[top[u]]) {
            if (sz[top[u]] > sz[top[v]]) swap(u, v);
            res += seg.prod(in[top[u]], in[u] + 1);
        }
        if (in[u] > in[v]) swap(u, v);
        res += seg.prod(in[u] + 1, in[v] + 1);
        return res;
    };

    dsu.clear();

    for (const auto& [u, v] : queries)
        if (u >= 0) {
            if (!dsu.merge(u, v))
                develop(u, v);
        } else
            cout << (dsu.find(~u) == dsu.find(~v) ? counting(~u, ~v) : -1) << '\n';
}

Compilation message

road_development.cpp: In lambda function:
road_development.cpp:166:22: warning: unused variable 'len' [-Wunused-variable]
  166 |         int res = 0, len = dep[u] + dep[v];
      |                      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 456 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 16192 KB Output is correct
2 Correct 587 ms 15804 KB Output is correct
3 Correct 265 ms 21372 KB Output is correct
4 Correct 252 ms 21604 KB Output is correct
5 Correct 299 ms 19628 KB Output is correct
6 Correct 249 ms 19828 KB Output is correct
7 Correct 530 ms 16068 KB Output is correct
8 Correct 249 ms 19424 KB Output is correct
9 Correct 457 ms 15628 KB Output is correct
10 Correct 252 ms 18532 KB Output is correct
11 Correct 233 ms 20696 KB Output is correct
12 Correct 221 ms 23316 KB Output is correct
13 Correct 199 ms 23760 KB Output is correct
14 Correct 252 ms 20188 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 16084 KB Output is correct
2 Correct 396 ms 15812 KB Output is correct
3 Correct 283 ms 20164 KB Output is correct
4 Correct 217 ms 22224 KB Output is correct
5 Correct 243 ms 15872 KB Output is correct
6 Correct 269 ms 20108 KB Output is correct
7 Correct 212 ms 16024 KB Output is correct
8 Correct 291 ms 19128 KB Output is correct
9 Correct 212 ms 19396 KB Output is correct
10 Correct 250 ms 21132 KB Output is correct
11 Correct 213 ms 15764 KB Output is correct
12 Correct 258 ms 21208 KB Output is correct
13 Correct 255 ms 21556 KB Output is correct
14 Correct 216 ms 20716 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 13760 KB Output is correct
2 Correct 353 ms 13636 KB Output is correct
3 Correct 190 ms 17324 KB Output is correct
4 Correct 192 ms 19160 KB Output is correct
5 Correct 603 ms 15436 KB Output is correct
6 Correct 262 ms 21060 KB Output is correct
7 Correct 58 ms 11400 KB Output is correct
8 Correct 74 ms 15940 KB Output is correct
9 Correct 76 ms 18292 KB Output is correct
10 Correct 138 ms 13912 KB Output is correct
11 Correct 234 ms 18884 KB Output is correct
12 Correct 273 ms 19272 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 456 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 247 ms 16192 KB Output is correct
10 Correct 587 ms 15804 KB Output is correct
11 Correct 265 ms 21372 KB Output is correct
12 Correct 252 ms 21604 KB Output is correct
13 Correct 299 ms 19628 KB Output is correct
14 Correct 249 ms 19828 KB Output is correct
15 Correct 530 ms 16068 KB Output is correct
16 Correct 249 ms 19424 KB Output is correct
17 Correct 457 ms 15628 KB Output is correct
18 Correct 252 ms 18532 KB Output is correct
19 Correct 233 ms 20696 KB Output is correct
20 Correct 221 ms 23316 KB Output is correct
21 Correct 199 ms 23760 KB Output is correct
22 Correct 252 ms 20188 KB Output is correct
23 Correct 282 ms 16084 KB Output is correct
24 Correct 396 ms 15812 KB Output is correct
25 Correct 283 ms 20164 KB Output is correct
26 Correct 217 ms 22224 KB Output is correct
27 Correct 243 ms 15872 KB Output is correct
28 Correct 269 ms 20108 KB Output is correct
29 Correct 212 ms 16024 KB Output is correct
30 Correct 291 ms 19128 KB Output is correct
31 Correct 212 ms 19396 KB Output is correct
32 Correct 250 ms 21132 KB Output is correct
33 Correct 213 ms 15764 KB Output is correct
34 Correct 258 ms 21208 KB Output is correct
35 Correct 255 ms 21556 KB Output is correct
36 Correct 216 ms 20716 KB Output is correct
37 Correct 155 ms 13760 KB Output is correct
38 Correct 353 ms 13636 KB Output is correct
39 Correct 190 ms 17324 KB Output is correct
40 Correct 192 ms 19160 KB Output is correct
41 Correct 603 ms 15436 KB Output is correct
42 Correct 262 ms 21060 KB Output is correct
43 Correct 58 ms 11400 KB Output is correct
44 Correct 74 ms 15940 KB Output is correct
45 Correct 76 ms 18292 KB Output is correct
46 Correct 138 ms 13912 KB Output is correct
47 Correct 234 ms 18884 KB Output is correct
48 Correct 273 ms 19272 KB Output is correct
49 Correct 253 ms 16156 KB Output is correct
50 Correct 484 ms 16048 KB Output is correct
51 Correct 272 ms 21176 KB Output is correct
52 Correct 237 ms 23384 KB Output is correct
53 Correct 219 ms 15280 KB Output is correct
54 Correct 248 ms 15180 KB Output is correct
55 Correct 252 ms 19908 KB Output is correct
56 Correct 212 ms 21452 KB Output is correct
57 Correct 253 ms 19228 KB Output is correct
58 Correct 235 ms 19360 KB Output is correct
59 Correct 241 ms 19780 KB Output is correct
60 Correct 207 ms 20828 KB Output is correct
61 Correct 226 ms 20888 KB Output is correct