oj.uz

Submission #703166

# Submission time Handle Problem Language Result Execution time Memory
703166 2023-02-26T10:22:05 Z Cyanmond Dynamic Diameter (CEOI19_diameter) C++17
42 / 100
 5000 ms 286424 KB 
#include <bits/stdc++.h>

using i64 = long long;
struct Edge {
    int to;
    i64 w;
};

using T = std::pair<i64, int>;
T op(T a, T b) {
    return std::max(a, b);
}
T e() {
    return {0, 0};
}
using U = i64;
T map(i64 a, T b) {
    return {b.first + a, b.second};
}
i64 composite(i64 a, i64 b) {
    return a + b;
}
i64 id() {
    return 0;
}

class lazySegtree {
    int n, logn, size;
    std::vector<T> node;
    std::vector<U> lazy;

    void update(int i) {
        node[i] = op(node[2 * i], node[2 * i + 1]);
    }

    void all_apply(int i, U f) {
        node[i] = map(f, node[i]);
        if (i < size) lazy[i] = composite(f, lazy[i]);
    }

    void push(int i) {
        all_apply(2 * i, lazy[i]);
        all_apply(2 * i + 1, lazy[i]);
        lazy[i] = id();
    }

    public:
    lazySegtree() {}

    lazySegtree(std::vector<T> initVec) {
        n = (int)initVec.size();
        logn = 0;
        while ((1 << logn) < n) {
            ++logn;
        }
        size = 1 << logn;
        node.assign(2 * size, e());
        lazy.assign(size, id());
        std::copy(initVec.begin(), initVec.end(), node.begin() + size);
        for (int i = size - 1; i >= 1; --i) {
            update(i);
        }
    }

    void apply(int l, int r, U f) {
        l += size, r += size;
        for (int d = logn; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }
        int l2 = l, r2 = r;
        while (l < r) {
            if (l & 1) all_apply(l++, f);
            if (r & 1) all_apply(--r, f);
            l /= 2;
            r /= 2;
        }
        l = l2, r = r2;
        for (int d = 1; d <= logn; ++d) {
            if (((l >> d) << d) != l) update(l >> d);
            if (((r >> d) << d) != r) update((r - 1) >> d);
        }
    }

    T fold(int l, int r) {
        l += size, r += size;
        for (int d = logn; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }
        T pl = e(), pr = e();
        while (l < r) {
            if (l & 1) pl = op(pl, node[l++]);
            if (r & 1) pr = op(node[--r], pr);
            l /= 2;
            r /= 2;
        }
        return op(pl, pr);
    }
};

struct TreeManager {
    int n;
    std::vector<std::vector<Edge>> tree;
    std::vector<bool> isOn, isCentroid;
    std::vector<int> size, in, out, fe, cen;
    std::vector<int> revIn;
    std::vector<i64> depth;

    TreeManager() {}

    TreeManager(const std::vector<std::vector<Edge>> &tree_, std::vector<bool> ison, std::vector<int> roots) {
        isOn = ison;
        tree = tree_;
        n = tree.size();
        isCentroid.assign(n, false);
        size.assign(n, -1);
        in.assign(n, -1);
        out.assign(n, -1);
        depth.assign(n, 0);
        fe.assign(n, 0);
        cen.assign(n, 0);
        int id = 0;
        for (const int v : roots) {
            dfs1(v, -1);
            int x = findCentroid(v, -1, size[v]);
            dfs2(x, -1, id, 0, -1, x);
        }
        revIn.resize(n);
        for (int i = 0; i < n; ++i) {
            if (in[i] >= 0) {
                revIn[in[i]] = i;
            }
        }
    }

    void dfs1(int v, int p) {
        size[v] = 1;
        for (const auto &[t, w] : tree[v]) {
            if (t == p or (not isOn[t])) {
                continue;
            }
            dfs1(t, v);
            size[v] += size[t];
        }
    }

    int findCentroid(int v, int p, int as) {
        bool isCent = true;
        for (const auto &[t, w] : tree[v]) {
            if (t == p or (not isOn[t])) {
                continue;
            }
            int res = findCentroid(t, v, as);
            if (res != -1) {
                return res;
            }
            if (size[t] > as / 2) {
                isCent = false;
            }
        }
        if ((as - size[v]) > as / 2) {
            isCent = false;
        }
        isCentroid[v] = isCent;
        return isCent ? v : -1;
    }

    void dfs2(int v, int p, int &id, i64 d, int f, int ce) {
        fe[v] = f;
        in[v] = id++;
        cen[v] = ce;
        depth[v] = d;
        for (const auto &[t, w] : tree[v]) {
            if (t == p or (not isOn[t])) {
                continue;
            }
            dfs2(t, v, id, d + w, (f == -1 ? t : f), ce);
        }
        out[v] = id;
    }
};

int main() {
    int N, Q;
    i64 W;
    std::cin >> N >> Q >> W;
    std::vector<int> A(N - 1), B(N - 1);
    std::vector<i64> C(N - 1);
    std::vector<std::vector<Edge>> tree(N);
    for (int i = 0; i < N - 1; ++i) {
        std::cin >> A[i] >> B[i] >> C[i];
        --A[i], --B[i];
        tree[A[i]].push_back({B[i], C[i]});
        tree[B[i]].push_back({A[i], C[i]});
    }

    std::vector<bool> isOn(N, true);
    std::vector<int> roots = {0};
    std::vector<TreeManager> managers;
    while (true) {
        TreeManager mng(tree, isOn, roots);
        roots.clear();
        for (int i = 0; i < N; ++i) {
            if (not mng.isCentroid[i]) {
                continue;
            }
            isOn[i] = false;
            for (const auto &[t, w] : tree[i]) {
                if (not isOn[t]) {
                    continue;
                }
                roots.push_back(t);
            }
        }
        managers.push_back(std::move(mng));
        if (std::none_of(isOn.begin(), isOn.end(), [](bool b) {
            return b;
        })) {
            break;
        }
    }
    const int m = (int)managers.size();
    std::vector<lazySegtree> segs(m);
    std::multiset<i64> diameters;
    for (int x = 0; x < m; ++x) {
        auto &mng = managers[x];
        std::vector<std::pair<i64, int>> weighVec(N);
        for (int i = 0; i < N; ++i) {
            if (mng.in[i] == -1) {
                continue;
            }
            weighVec[mng.in[i]].first = mng.depth[i];
        }
        for (int i = 0; i < N; ++i) {
            weighVec[i].second = i;
        }
        segs[x] = lazySegtree(weighVec);

        for (int i = 0; i < N; ++i) {
            if (not mng.isCentroid[i]) {
                continue;
            }
            if (mng.size[i] == 1) {
                continue;
            }
            const int bl = mng.in[i], br = mng.out[i];
            const auto [v, p] = segs[x].fold(bl, br);
            const int l = mng.in[mng.fe[mng.revIn[p]]], r = mng.out[mng.fe[mng.revIn[p]]];
            const auto v2 = std::max(segs[x].fold(bl, l).first, segs[x].fold(r, br).first);
            diameters.insert(v + v2);
        }
    }

    i64 last = 0;
    while (Q--) {
        int d;
        i64 e;
        std::cin >> d >> e;
        i64 i = (last + d) % (N - 1);
        i64 w = (last + e) % W;
        // int i = d;
        // i64 w = e;
        int a = A[i], b = B[i];
        for (int x = 0; x < m; ++x) {
            auto &mng = managers[x];
            if ((not mng.isOn[a]) or (not mng.isOn[b])) {
                break;
            }
            if (mng.depth[a] > mng.depth[b]) {
                std::swap(a, b);
            }
            const int c = mng.cen[a];
            if (mng.size[c] == 1) {
                break;
            }
            const int bl = mng.in[c], br = mng.out[c];
            const auto [v, p] = segs[x].fold(bl, br);
            const int l = mng.in[mng.fe[mng.revIn[p]]], r = mng.out[mng.fe[mng.revIn[p]]];
            const auto v2 = std::max(segs[x].fold(bl, l).first, segs[x].fold(r, br).first);
            diameters.erase(diameters.find(v + v2));

            segs[x].apply(mng.in[b], mng.out[b], (w - C[i]));
            const auto [v3, p3] = segs[x].fold(bl, br);
            const int l2 = mng.in[mng.fe[mng.revIn[p3]]], r2 = mng.out[mng.fe[mng.revIn[p3]]];
            const auto v4 = std::max(segs[x].fold(bl, l2).first, segs[x].fold(r2, br).first);
            diameters.insert(v3 + v4);
        }
        C[i] = w;
        last = *diameters.rbegin();
        std::cout << last << std::endl;
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 436 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 436 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 36 ms 1796 KB Output is correct
20 Correct 37 ms 1792 KB Output is correct
21 Correct 43 ms 1876 KB Output is correct
22 Correct 48 ms 1972 KB Output is correct
23 Correct 63 ms 9532 KB Output is correct
24 Correct 81 ms 11200 KB Output is correct
25 Correct 95 ms 11984 KB Output is correct
26 Correct 96 ms 12288 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 300 KB Output is correct
3 Correct 5 ms 308 KB Output is correct
4 Correct 40 ms 508 KB Output is correct
5 Correct 197 ms 1352 KB Output is correct
6 Runtime error 1 ms 468 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1748 KB Output is correct
2 Correct 64 ms 1876 KB Output is correct
3 Correct 301 ms 2364 KB Output is correct
4 Correct 596 ms 3184 KB Output is correct
5 Correct 42 ms 23560 KB Output is correct
6 Correct 137 ms 23772 KB Output is correct
7 Correct 584 ms 24380 KB Output is correct
8 Correct 1099 ms 25276 KB Output is correct
9 Correct 197 ms 124172 KB Output is correct
10 Correct 347 ms 124212 KB Output is correct
11 Correct 1016 ms 124832 KB Output is correct
12 Correct 1850 ms 125844 KB Output is correct
13 Correct 397 ms 263016 KB Output is correct
14 Correct 587 ms 263224 KB Output is correct
15 Correct 1415 ms 264000 KB Output is correct
16 Correct 2430 ms 265024 KB Output is correct
17 Correct 4771 ms 264656 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3524 ms 265644 KB Output is correct
2 Correct 3799 ms 265404 KB Output is correct
3 Correct 3551 ms 250216 KB Output is correct
4 Correct 3738 ms 280668 KB Output is correct
5 Correct 3567 ms 265412 KB Output is correct
6 Correct 3353 ms 264648 KB Output is correct
7 Correct 4693 ms 282760 KB Output is correct
8 Correct 4781 ms 282948 KB Output is correct
9 Correct 4832 ms 282756 KB Output is correct
10 Correct 4666 ms 282864 KB Output is correct
11 Correct 4661 ms 282784 KB Output is correct
12 Correct 4252 ms 281572 KB Output is correct
13 Execution timed out 5084 ms 286424 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 436 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 36 ms 1796 KB Output is correct
20 Correct 37 ms 1792 KB Output is correct
21 Correct 43 ms 1876 KB Output is correct
22 Correct 48 ms 1972 KB Output is correct
23 Correct 63 ms 9532 KB Output is correct
24 Correct 81 ms 11200 KB Output is correct
25 Correct 95 ms 11984 KB Output is correct
26 Correct 96 ms 12288 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 2 ms 300 KB Output is correct
29 Correct 5 ms 308 KB Output is correct
30 Correct 40 ms 508 KB Output is correct
31 Correct 197 ms 1352 KB Output is correct
32 Runtime error 1 ms 468 KB Execution killed with signal 11
33 Halted 0 ms 0 KB -