Submission #1006314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006314		ttttttttttttth	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5059 ms	428932 KiB

diameter

// Author: Ivan Teo
// Created: Sun Jun 23 11:05:28 2024

#define TASKNAME "1192B"
#include <bits/stdc++.h>
using namespace std;

#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define el cerr << "\n=========================================\n"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
    assert(l <= r);
    return uniform_int_distribution<int> (l, r)(rng);
}

#define idl (id << 1)
#define idr (id << 1 | 1)
struct SegmentTree
{
    int n;
    vector<ii> st;
    vi lz;

    SegmentTree() {}
    SegmentTree(int n): n(n), st(4 * n + 5), lz(4 * n + 5)
    {
        build(1, 1, n);
    }

    void add(int id, int v)
    {
        st[id].fi += v;
        lz[id] += v;
    }

    void push(int id)
    {
        add(idl, lz[id]);
        add(idr, lz[id]);
        lz[id] = 0;
    }

    void build(int id, int l, int r)
    {
        if (l > r) return ;
        if (l == r) return (void)(st[id] = {0, l});
        int m = l + r >> 1;
        build(idl, l, m);
        build(idr, m + 1, r);
        st[id] = max(st[idl], st[idr]);
    }

    void add(int id, int l, int r, int tl, int tr, int v)
    {
        if (l > r || l > tr || r < tl) return ;
        if (l >= tl && r <= tr) return (void)(add(id, v));
        push(id);
        int m = l + r >> 1;
        add(idl, l, m, tl, tr, v);
        add(idr, m + 1, r, tl, tr, v);
        st[id] = max(st[idl], st[idr]);
    }

    ii get(int id, int l, int r, int tl, int tr)
    {
        if (l > r || l > tr || r < tl) return {};
        if (l >= tl && r <= tr) return st[id];
        push(id);
        int m = l + r >> 1;
        return max(get(idl, l, m, tl, tr), get(idr, m + 1, r, tl, tr));
    }

    void add(int l, int r, int v)
    {
        add(1, 1, n, l, r, v);
    }

    ii get(int l, int r)
    {
        return get(1, 1, n, l, r);
    }

    ii get()
    {
        return st[1];
    }
};

using iii = tuple<int, int, int>;

struct Tree
{
    vector<iii> e;
    vector<vector<ii>> g;
    vi dep, branch, in, out, pw, l, inv;
    SegmentTree st;
    int n, root, timer = 0;
    set<ii> s;

    Tree() {}
    Tree(vector<iii> e, int root): e(e), root(root)
    {
        build();
    }

    void dfs(int u, int p)
    {
        in[u] = ++timer;
        inv[timer] = u;
        if (p == root) branch[u] = u;
        else if (u != root) branch[u] = branch[p];
        for (auto &[v, w] : g[u]) if (v != p)
            {
                dep[v] = dep[u] + w;
                pw[v] = w;
                dfs(v, u);
            }
        out[u] = timer;
    }

    void build()
    {
        for (auto &[u, v, w] : e) l.pb(u), l.pb(v);
        sort(alll(l));
        l.erase(unique(alll(l)), l.end());
        n = sz(l);
        g = vector<vector<ii>>(n + 1);
        inv = pw = in = out = dep = branch = vi(n + 1);
        st = SegmentTree(n);
        for (auto &[u, v, w] : e)
        {
            s.insert({u, v});
            s.insert({v, u});
            u = lower_bound(alll(l), u) - l.begin() + 1;
            v = lower_bound(alll(l), v) - l.begin() + 1;
            g[u].pb(v, w);
            g[v].pb(u, w);
        }
        root = lower_bound(alll(l), root) - l.begin() + 1;
        dfs(root, 0);
        fore(i, 1, n) st.add(in[i], in[i], dep[i]);
    }

    void upd(int u, int v, int w)
    {
        if (s.find(ii(u, v)) == s.end()) return ;
        u = lower_bound(alll(l), u) - l.begin() + 1;
        v = lower_bound(alll(l), v) - l.begin() + 1;
        if (in[u] > in[v]) swap(u, v);
        st.add(in[v], out[v], w - pw[v]);
        pw[v] = w;
    }

    int get()
    {
        auto [dist, u] = st.get();
        u = inv[u];
        dist += max(st.get(1, in[branch[u]] - 1).fi, st.get(out[branch[u]] + 1, n).fi);
        return dist;
    }
};

void solve()
{
    int n, q, W;
    cin >> n >> q >> W;
    vector<vector<ii>> g(n + 1);
    vector<ii> edge;
    fore(i, 1, n - 1)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb(v, w);
        g[v].pb(u, w);
        edge.pb(u, v);
    }
    vi sz = vi(n + 1), del(n + 1);

    function<int(int, int, int)> centroid = [&](int u, int p, int n)
    {
        for (auto &[v, w] : g[u]) if (!del[v] && v != p)
                if (sz[v] * 2 > n) return centroid(v, u, n);
        return u;
    };

    function<void(int, int)> dfs = [&](int u, int p)
    {
        sz[u] = 1;
        for (auto &[v, w] : g[u]) if (!del[v] && v != p)
                dfs(v, u), sz[u] += sz[v];
    };

    vector<iii> e;

    function<void(int, int)> add = [&](int u, int p)
    {
        for (auto &[v, w] : g[u]) if (!del[v] && v != p)
            add(v, u), e.pb(u, v, w);
    };

    vector<Tree> jungle;

    function<void(int)> go = [&](int u)
    {
        dfs(u, 0);
        int root = centroid(u, 0, sz[u]);
        del[root] = 1;
        e.clear();
        add(root, 0);
        if (sz(e)) jungle.pb(Tree(e, root));
        for (auto &[v, w] : g[root]) if (!del[v])
                go(v);
    };
    go(1);

    int last = 0;
    while (q--)
    {
        int id, w;
        cin >> id >> w;
        id = (id + last) % (n - 1);
        w = (w + last) % W;
        // db(edge[id].fi), db(edge[id].se), db(w), el;
        int ans = 0;
        for (auto &i : jungle) i.upd(edge[id].fi, edge[id].se, w), ans = max(ans, i.get());
        cout << ans << '\n';
        last = ans;
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    if (fopen(TASKNAME ".inp", "r"))
    {
        freopen(TASKNAME ".inp", "r", stdin);
        freopen(TASKNAME ".out", "w", stdout);
    }
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    el, cerr << "Execution Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s", el;
    return 0;
}

Compilation message (stderr)

diameter.cpp: In member function 'void SegmentTree::build(long long int, long long int, long long int)':
diameter.cpp:58:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int m = l + r >> 1;
      |                 ~~^~~
diameter.cpp: In member function 'void SegmentTree::add(long long int, long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:69:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int m = l + r >> 1;
      |                 ~~^~~
diameter.cpp: In member function 'ii SegmentTree::get(long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:80:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int m = l + r >> 1;
      |                 ~~^~~
diameter.cpp: In function 'int main()':
diameter.cpp:247:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  247 |         freopen(TASKNAME ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:248:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  248 |         freopen(TASKNAME ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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