oj.uz

Submission #703160

# Submission time Handle Problem Language Result Execution time Memory
703160 2023-02-26T09:50:59 Z Cyanmond Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 475 ms 36216 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(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;
    std::vector<int> revIn;
    std::vector<i64> depth;

    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);
        int id = 0;
        for (const int v : roots) {
            dfs1(v, -1);
            // int x = findCentroid(v, -1, size[v]);
            int x = 0;
            dfs2(x, -1, id, 0, -1);
        }
        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) {
        fe[v] = f;
        in[v] = id++;
        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));
        }
        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]});
    }

    // subtask 5
    TreeManager mng(tree, std::vector<bool>(N, true), {0});
    std::vector<std::pair<i64, int>> weighVec(N);
    for (int i = 0; i < N; ++i) {
        weighVec[mng.in[i]].first = mng.depth[i];
    }
    for (int i = 0; i < N; ++i) {
        weighVec[i].second = i;
    }
    lazySegtree seg(weighVec);

    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];
        if (mng.depth[a] > mng.depth[b]) std::swap(a, b);
        // b
        seg.apply(mng.in[b], mng.out[b], (w - C[i]));
        C[i] = w;

        const auto [v, p] = seg.fold(0, N);
        const int l = mng.in[mng.fe[mng.revIn[p]]], r = mng.out[mng.fe[mng.revIn[p]]];
        const auto v2 = std::max(seg.fold(0, l).first, seg.fold(r, N).first);
        last = v + v2;
        std::cout << last << std::endl;
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 43 ms 492 KB Output is correct
5 Correct 189 ms 1376 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 5 ms 444 KB Output is correct
10 Correct 43 ms 644 KB Output is correct
11 Correct 209 ms 1720 KB Output is correct
12 Correct 4 ms 1748 KB Output is correct
13 Correct 5 ms 1748 KB Output is correct
14 Correct 10 ms 1748 KB Output is correct
15 Correct 54 ms 2008 KB Output is correct
16 Correct 239 ms 3316 KB Output is correct
17 Correct 82 ms 28196 KB Output is correct
18 Correct 80 ms 28096 KB Output is correct
19 Correct 85 ms 28124 KB Output is correct
20 Correct 136 ms 28300 KB Output is correct
21 Correct 338 ms 28492 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 31636 KB Output is correct
2 Correct 435 ms 31392 KB Output is correct
3 Correct 460 ms 31576 KB Output is correct
4 Correct 421 ms 31424 KB Output is correct
5 Correct 431 ms 31508 KB Output is correct
6 Correct 423 ms 31652 KB Output is correct
7 Correct 444 ms 33084 KB Output is correct
8 Correct 446 ms 33172 KB Output is correct
9 Correct 475 ms 33200 KB Output is correct
10 Correct 444 ms 33124 KB Output is correct
11 Correct 433 ms 33108 KB Output is correct
12 Correct 415 ms 32532 KB Output is correct
13 Correct 449 ms 36088 KB Output is correct
14 Correct 450 ms 36216 KB Output is correct
15 Correct 439 ms 35916 KB Output is correct
16 Correct 447 ms 35928 KB Output is correct
17 Correct 454 ms 35500 KB Output is correct
18 Correct 442 ms 33392 KB Output is correct
19 Correct 471 ms 36044 KB Output is correct
20 Correct 463 ms 35956 KB Output is correct
21 Correct 453 ms 36076 KB Output is correct
22 Correct 460 ms 36008 KB Output is correct
23 Correct 448 ms 35268 KB Output is correct
24 Correct 423 ms 33396 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -