제출 #1033402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1033402		Fatonim	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	540 ms	370444 KiB

diameter

// "We create our own demons"
#include <bits/stdc++.h>

using namespace std;

#ifdef ONPC
#include "debug.h"
#else
#define dbg(...)
#endif

#define int long long
#define ll long long
#define ld long double
#define pi pair<int, int>
// vector
#define sz(a) (int)((a).size())
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxpos(x) (max_element(all(x)) - x.begin())
#define minpos(x) (min_element(all(x)) - x.begin())
#define rev(x) (reverse(all(x)))
// bits
#define popcount(n) __builtin_popcountll(n)
#define clz(n) __builtin_clzll(n)
// math
#define sqr(n) ((n) * (n))
#define divup(a, b) (((a) + (b)-1) / (b))
// ostream
#define Fixed(a) cout << fixed << setprecision(12) << a;

template <class T> bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool chmax(T& a, const T& b) { return b > a ? a = b, 1 : 0; }

template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T> using max_queue = priority_queue<T, vector<T>, less<T>>;

template <class T> using V = vector<T>;
using vi = V<int>;
using vd = V<ld>;
using vb = V<bool>;
using vpi = V<pi>;
using vvi = V<vi>;
using vvb = V<vb>;

const int mod = 1e9 + 7; // 998244353 1e9 + 7
const ll inf = (int)(1e18) + 7;
const int inf_s = 1e9 + 7;
const ld eps = 1e-9;

const int B = 32;
const int N = 1000 + 3;
const int logn = 20;
const int maxn = 1e5 + 7;
/////////////////////////solve/////////////////////////

struct segtree {
public:
    struct node {
        int mx = 0;
        int add = 0;
        void apply(int tl, int tr, int x) {
            mx += x;
            add += x;
        }
    };
private:
    int n;
    V<node> tree;

    node unite(const node& a, const node& b) {
        node res;
        res.mx = max(a.mx, b.mx);
        return res;
    }

    void push(int v, int tl, int tr) {
        int tm = (tl + tr) >> 1;

        if (tree[v].add != 0) {
            tree[2 * v].apply(tl, tm, tree[v].add);
            tree[2 * v + 1].apply(tm, tr, tree[v].add);
            tree[v].add = 0;
        }
    }

    template <class T>
    void build(const V<T>& a, int v, int tl, int tr) {
        if (tr - tl == 1) {
            tree[v].apply(tl, tr, a[tl]);
            return;
        }
        int tm = (tl + tr) >> 1;
        build(a, 2 * v, tl, tm);
        build(a, 2 * v + 1, tm, tr);
        tree[v] = unite(tree[2 * v], tree[2 * v + 1]);
    }

    void build(int v, int tl, int tr) {
        if (tr - tl == 1) {
            return;
        }
        int tm = (tl + tr) >> 1;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm, tr);
        tree[v] = unite(tree[2 * v], tree[2 * v + 1]);
    }

    template <class T>
    void update(int l, int r, const T& x, int v, int tl, int tr) {
        if (tl >= r || tr <= l) return;
        if (tl >= l && tr <= r) {
            tree[v].apply(tl, tr, x);
            return;
        }
        int tm = (tl + tr) >> 1;
        push(v, tl, tr);
        update(l, r, x, 2 * v, tl, tm);
        update(l, r, x, 2 * v + 1, tm, tr);
        tree[v] = unite(tree[2 * v], tree[2 * v + 1]);
    }

    node get(int l, int r, int v, int tl, int tr) {
        if (tl >= l && tr <= r) return tree[v];
        int tm = (tl + tr) >> 1;
        push(v, tl, tr);
        if (tm <= l) return get(l, r, 2 * v + 1, tm, tr);
        if (tm >= r) return get(l, r, 2 * v, tl, tm);
        return unite(get(l, r, 2 * v, tl, tm),
            get(l, r, 2 * v + 1, tm, tr));
    }

public:
    segtree(int n = 0) : n(n) {
        if (n == 0) return;
        tree.resize(4 * n);
        build(1, 0, n);
    }

    template <class T>
    segtree(const V<T>& a) {
        n = sz(a);
        tree.resize(4 * n);
        build(a, 1, 0, n);
    }

    template <class T>
    void update(int l, int r, const T& x) {
        update(l, r + 1, x, 1, 0, n);
    }

    template <class T>
    void update(int i, const T& x) {
        update(i, i + 1, x, 1, 0, n);
    }

    node get(int l, int r) {
        return get(l, r + 1, 1, 0, n);
    }

    node get(int i) {
        return get(i, i + 1, 1, 0, n);
    }
};

vpi g[maxn];
pair<pi, int> e[maxn];

segtree st[logn];
bool used[maxn];
int tim[logn];
int sz[maxn], h[maxn], pr[maxn], id[maxn];
int tin[logn][maxn], tout[logn][maxn], tour[logn][maxn];
multiset <int, greater<int>> ms[maxn];
multiset <int, greater<int>> best;

int dfs1(int v, int p = -1) {
    sz[v] = 1;
    for (auto& [u, w] : g[v]) {
        if (u != p && !used[u]) {
            sz[v] += dfs1(u, v);
        }
    }
    return sz[v];
}

int dfs2(int v, int n, int p = -1) {
    for (auto& [u, w] : g[v]) {
        if (u != p && !used[u] && sz[u] > n / 2)
            return dfs2(u, n, v);
    }
    return v;
}

int calc(int v) {
    int res = 0;
    if (sz(ms[v]) > 0) res += *ms[v].begin();
    if (sz(ms[v]) > 1) res += *(++ms[v].begin());
    return res;
}

void decompose(int v, int d = 0, int p = -1) {
    int n = dfs1(v);
    int c = dfs2(v, n);
    id[c] = v, v = c;
    id[c] = c;
    h[v] = d;
    pr[v] = p;
    used[v] = 1;

    function<void(int, int, int)> dfs = [&](int v, int x, int p) {
        tin[d][v] = ++tim[d];
        tour[d][tim[d]] = v;
        st[d].update(tin[d][v], x);
        for (auto& [u, w] : g[v]) {
            if (u != p && !used[u]) dfs(u, x + w, v);
        }
        tout[d][v] = tim[d];
    };

    for (auto& [u, w] : g[v]) {
        if (!used[u]) {
            dfs(u, w, v);
            ms[v].insert(st[d].get(tin[d][u], tout[d][u]).mx);
        }
    }
    best.insert(calc(v));

    for (auto& [u, w] : g[v]) {
        if (!used[u]) {
            decompose(u, d + 1, v);
        }
    }
}

void solve() {
    int n, q, m;
    cin >> n >> q >> m;

    for (int i = 0; i < n - 1; ++i) {
        int v, u, w;
        cin >> v >> u >> w;
        --v; --u;

        g[v].push_back({u, w});
        g[u].push_back({v, w});
        e[i] = {{v, u}, w};
    };

    for (int i = 0; i < logn; ++i) {
        st[i] = segtree(n);
        tim[i] = -1;
    }
    decompose(0);

    int ans = 0;
    while (q--) {
        int i, nw;
        cin >> i >> nw;
        i = (i + ans) % (n - 1);
        nw = (nw + ans) % m;
        dbg(i, nw);

        auto [v, u] = e[i].first;
        int w = e[i].second;
        e[i].second = nw;
        if (h[u] < h[v]) swap(v, u);

        int ch = u;
        while (pr[ch] != v) {
            ch = pr[ch];
        }

        dbg(u, v, ch);

        while (v != -1) {
            int d = h[v];
            dbg(v, d);

            best.erase(best.find(calc(v)));
            ms[v].erase(ms[v].find(st[d].get(tin[d][id[ch]], tout[d][id[ch]]).mx));
            st[d].update(tin[d][u], tout[d][u], nw - w);
            ms[v].insert(st[d].get(tin[d][id[ch]], tout[d][id[ch]]).mx);
            best.insert(calc(v));

            ch = v;
            v = pr[v];
        }

        ans = *best.begin();
        cout << ans << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ONPC
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif

    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; ++i) {
#ifdef ONPC
        cerr << "===========" << i << "===========" << '\n';
#endif
        solve();
    }

#ifdef ONPC
    cerr << endl << "Time " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27