제출 #1365095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1365095		msab3f	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	535 ms	80488 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Edge {
    int u, v;
    ll w;
};

const int MAX_N = 100'000 + 10;

int n, q, st[MAX_N], ft[MAX_N];
ll max_w, last;
vector<int> adj[MAX_N], tour;
Edge edges[MAX_N];

void dfs(int u, int p) {
    static int ptr = 0;
    st[u] = ptr++;
    tour.push_back(u);
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
            tour.push_back(u);
            ptr++;
        }
    }
    ft[u] = ptr;
}

namespace Seg {
    struct Node {
        vector<ll> dp;
        Node() : dp(5) { }
        Node(const Node& lc, const Node& rc) : dp(5) {
            dp[0] = max(lc.dp[0], rc.dp[0]);
            dp[1] = max(lc.dp[1], rc.dp[1]);
            dp[2] = max({lc.dp[2], rc.dp[2], lc.dp[0] + rc.dp[1]});
            dp[3] = max({lc.dp[3], rc.dp[3], lc.dp[1] + rc.dp[0]});
            dp[4] = max({lc.dp[4], rc.dp[4], lc.dp[2] + rc.dp[0], lc.dp[0] + rc.dp[3]});
        }
        inline void apply(ll x) {
            dp[0] += x;
            dp[1] -= 2 * x;
            dp[2] -= x;
            dp[3] -= x;
        }
    } tree[8 * MAX_N];
    ll lazy[8 * MAX_N];

#define mid (l + r) >> 1
#define lc id << 1
#define rc (lc | 1)

    void add(int ql, int qr, ll x, int id = 1, int l = 0, int r = int(tour.size())) {
        if (ql <= l && r <= qr) {
            tree[id].apply(x);
            lazy[id] += x;
        } else {
            if (ql < mid) {
                add(ql, qr, x, lc, l, mid);
            }
            if (mid < qr) {
                add(ql, qr, x, rc, mid, r);
            }
            tree[id] = {tree[lc], tree[rc]};
            tree[id].apply(lazy[id]);
        }
    }

    ll get() { return tree[1].dp[4]; }
}

int main() {
    cin >> n >> q >> max_w;

    for (int e = 1; e <= n - 1; ++e) {
        auto &[u, v, w] = edges[e];
        cin >> u >> v >> w;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, -1);

    for (int e = 1; e <= n - 1; ++e) {
        auto &[u, v, w] = edges[e];
        if (st[u] > st[v]) swap(u, v);
        Seg::add(st[v], ft[v], w);
    }

    while (q--) {
        int d;
        ll e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % max_w;
        auto &[u, v, w] = edges[d + 1];
        Seg::add(st[v], ft[v], e - w);
        w = e;
        last = Seg::get();
        cout << last << '\n';
    }
}

• 서브태스크 1: 11 / 11
• 서브태스크 2: 13 / 13
• 서브태스크 3: 7 / 7
• 서브태스크 4: 18 / 18
• 서브태스크 5: 24 / 24
• 서브태스크 6: 27 / 27