답안 #703174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
703174	2023-02-26T10:41:37 Z	Cyanmond	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	4722 ms	169868 KB

diameter

#pragma GCC target("avx2")
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

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

using T = std::pair<i64, int>;
T op(const T& a, const T& b) {
    return std::max(a, b);
}
T e() {
    return {0, 0};
}
using U = i64;
T map(i64 a, const 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);
    }
};

std::vector<std::vector<Edge>> tree;

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

    TreeManager() {}

    TreeManager(const std::vector<char> &ison, const std::vector<int> &roots) {
        isOn = ison;
        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;
        size[v] = 1;
        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);
            size[v] += size[t];
        }
        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);
    tree.resize(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<char> isOn(N, true);
    std::vector<int> roots = {0};
    std::vector<TreeManager> managers;
    while (true) {
        TreeManager mng(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;
    std::vector<i64> memoDiameters(N);
    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);
            memoDiameters[i] = 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 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;
            }
            diameters.erase(diameters.find(memoDiameters[c]));
            segs[x].apply(mng.in[b], mng.out[b], (w - C[i]));
            const int bl = mng.in[c], br = mng.out[c];
            const auto [v3, p3] = segs[x].fold(bl, br);
            const int l = mng.in[mng.fe[mng.revIn[p3]]], r = mng.out[mng.fe[mng.revIn[p3]]];
            const auto v2 = std::max(segs[x].fold(bl, l).first, segs[x].fold(r, br).first);
            diameters.insert(v3 + v2);
            memoDiameters[c] = v3 + v2;
        }
        C[i] = w;
        last = *diameters.rbegin();
        std::cout << last << std::endl;
    }
}

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	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	212 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	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 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	340 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

#	결과	실행 시간	메모리	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	212 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	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 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	340 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	29 ms	1128 KB	Output is correct
20	Correct	30 ms	1136 KB	Output is correct
21	Correct	36 ms	1108 KB	Output is correct
22	Correct	42 ms	1220 KB	Output is correct
23	Correct	48 ms	6020 KB	Output is correct
24	Correct	59 ms	7028 KB	Output is correct
25	Correct	69 ms	7528 KB	Output is correct
26	Correct	76 ms	7708 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	4 ms	212 KB	Output is correct
4	Correct	40 ms	340 KB	Output is correct
5	Correct	187 ms	716 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	44 ms	468 KB	Output is correct
11	Correct	214 ms	832 KB	Output is correct
12	Correct	5 ms	1948 KB	Output is correct
13	Correct	5 ms	1876 KB	Output is correct
14	Correct	9 ms	1972 KB	Output is correct
15	Correct	52 ms	1924 KB	Output is correct
16	Correct	242 ms	2376 KB	Output is correct
17	Correct	87 ms	30536 KB	Output is correct
18	Correct	93 ms	30560 KB	Output is correct
19	Correct	92 ms	30472 KB	Output is correct
20	Correct	140 ms	30616 KB	Output is correct
21	Correct	354 ms	31136 KB	Output is correct

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	1108 KB	Output is correct
2	Correct	56 ms	1124 KB	Output is correct
3	Correct	249 ms	1520 KB	Output is correct
4	Correct	497 ms	1536 KB	Output is correct
5	Correct	33 ms	14744 KB	Output is correct
6	Correct	109 ms	14748 KB	Output is correct
7	Correct	438 ms	15004 KB	Output is correct
8	Correct	845 ms	15276 KB	Output is correct
9	Correct	137 ms	72136 KB	Output is correct
10	Correct	262 ms	72232 KB	Output is correct
11	Correct	813 ms	72520 KB	Output is correct
12	Correct	1541 ms	72744 KB	Output is correct
13	Correct	280 ms	152336 KB	Output is correct
14	Correct	425 ms	152340 KB	Output is correct
15	Correct	1091 ms	152760 KB	Output is correct
16	Correct	1926 ms	152880 KB	Output is correct
17	Correct	4016 ms	153016 KB	Output is correct

Subtask #5
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2999 ms	152824 KB	Output is correct
2	Correct	3037 ms	153292 KB	Output is correct
3	Correct	3147 ms	144928 KB	Output is correct
4	Correct	3165 ms	161792 KB	Output is correct
5	Correct	3030 ms	153032 KB	Output is correct
6	Correct	2695 ms	151544 KB	Output is correct
7	Correct	4043 ms	163740 KB	Output is correct
8	Correct	3994 ms	163528 KB	Output is correct
9	Correct	4075 ms	163688 KB	Output is correct
10	Correct	4011 ms	163588 KB	Output is correct
11	Correct	3945 ms	163236 KB	Output is correct
12	Correct	3557 ms	161404 KB	Output is correct
13	Correct	4433 ms	165564 KB	Output is correct
14	Correct	4604 ms	169868 KB	Output is correct
15	Correct	4594 ms	169724 KB	Output is correct
16	Correct	4673 ms	169736 KB	Output is correct
17	Correct	4454 ms	169348 KB	Output is correct
18	Correct	3801 ms	167056 KB	Output is correct
19	Correct	4722 ms	169680 KB	Output is correct
20	Correct	4502 ms	169628 KB	Output is correct
21	Correct	4494 ms	169856 KB	Output is correct
22	Correct	4404 ms	169668 KB	Output is correct
23	Correct	4412 ms	169316 KB	Output is correct
24	Correct	3878 ms	167252 KB	Output is correct

Subtask #6
27.0 / 27.0

#	결과	실행 시간	메모리	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	212 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	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 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	340 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	29 ms	1128 KB	Output is correct
20	Correct	30 ms	1136 KB	Output is correct
21	Correct	36 ms	1108 KB	Output is correct
22	Correct	42 ms	1220 KB	Output is correct
23	Correct	48 ms	6020 KB	Output is correct
24	Correct	59 ms	7028 KB	Output is correct
25	Correct	69 ms	7528 KB	Output is correct
26	Correct	76 ms	7708 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	4 ms	212 KB	Output is correct
30	Correct	40 ms	340 KB	Output is correct
31	Correct	187 ms	716 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	5 ms	444 KB	Output is correct
36	Correct	44 ms	468 KB	Output is correct
37	Correct	214 ms	832 KB	Output is correct
38	Correct	5 ms	1948 KB	Output is correct
39	Correct	5 ms	1876 KB	Output is correct
40	Correct	9 ms	1972 KB	Output is correct
41	Correct	52 ms	1924 KB	Output is correct
42	Correct	242 ms	2376 KB	Output is correct
43	Correct	87 ms	30536 KB	Output is correct
44	Correct	93 ms	30560 KB	Output is correct
45	Correct	92 ms	30472 KB	Output is correct
46	Correct	140 ms	30616 KB	Output is correct
47	Correct	354 ms	31136 KB	Output is correct
48	Correct	7 ms	1108 KB	Output is correct
49	Correct	56 ms	1124 KB	Output is correct
50	Correct	249 ms	1520 KB	Output is correct
51	Correct	497 ms	1536 KB	Output is correct
52	Correct	33 ms	14744 KB	Output is correct
53	Correct	109 ms	14748 KB	Output is correct
54	Correct	438 ms	15004 KB	Output is correct
55	Correct	845 ms	15276 KB	Output is correct
56	Correct	137 ms	72136 KB	Output is correct
57	Correct	262 ms	72232 KB	Output is correct
58	Correct	813 ms	72520 KB	Output is correct
59	Correct	1541 ms	72744 KB	Output is correct
60	Correct	280 ms	152336 KB	Output is correct
61	Correct	425 ms	152340 KB	Output is correct
62	Correct	1091 ms	152760 KB	Output is correct
63	Correct	1926 ms	152880 KB	Output is correct
64	Correct	4016 ms	153016 KB	Output is correct
65	Correct	2999 ms	152824 KB	Output is correct
66	Correct	3037 ms	153292 KB	Output is correct
67	Correct	3147 ms	144928 KB	Output is correct
68	Correct	3165 ms	161792 KB	Output is correct
69	Correct	3030 ms	153032 KB	Output is correct
70	Correct	2695 ms	151544 KB	Output is correct
71	Correct	4043 ms	163740 KB	Output is correct
72	Correct	3994 ms	163528 KB	Output is correct
73	Correct	4075 ms	163688 KB	Output is correct
74	Correct	4011 ms	163588 KB	Output is correct
75	Correct	3945 ms	163236 KB	Output is correct
76	Correct	3557 ms	161404 KB	Output is correct
77	Correct	4433 ms	165564 KB	Output is correct
78	Correct	4604 ms	169868 KB	Output is correct
79	Correct	4594 ms	169724 KB	Output is correct
80	Correct	4673 ms	169736 KB	Output is correct
81	Correct	4454 ms	169348 KB	Output is correct
82	Correct	3801 ms	167056 KB	Output is correct
83	Correct	4722 ms	169680 KB	Output is correct
84	Correct	4502 ms	169628 KB	Output is correct
85	Correct	4494 ms	169856 KB	Output is correct
86	Correct	4404 ms	169668 KB	Output is correct
87	Correct	4412 ms	169316 KB	Output is correct
88	Correct	3878 ms	167252 KB	Output is correct
89	Correct	3069 ms	156428 KB	Output is correct
90	Correct	3321 ms	165192 KB	Output is correct
91	Correct	3891 ms	165720 KB	Output is correct
92	Correct	4121 ms	167076 KB	Output is correct
93	Correct	4293 ms	168044 KB	Output is correct
94	Correct	4294 ms	168472 KB	Output is correct
95	Correct	4519 ms	168388 KB	Output is correct
96	Correct	4447 ms	168188 KB	Output is correct
97	Correct	4438 ms	168264 KB	Output is correct
98	Correct	4466 ms	168992 KB	Output is correct
99	Correct	4534 ms	168324 KB	Output is correct
100	Correct	4628 ms	168268 KB	Output is correct

답안 #703174

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 13.0 / 13.0

Subtask #3 7.0 / 7.0

Subtask #4 18.0 / 18.0

Subtask #5 24.0 / 24.0

Subtask #6 27.0 / 27.0

Subtask #1
11.0 / 11.0

Subtask #2
13.0 / 13.0

Subtask #3
7.0 / 7.0

Subtask #4
18.0 / 18.0

Subtask #5
24.0 / 24.0

Subtask #6
27.0 / 27.0