Submission #1256837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256837		the_rizzler	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	96 ms	32840 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO { //by cyffff
int len = 0;
char ibuf[(1 << 21) + 1], *iS, *iT, out[(1 << 25) + 1];
#if ONLINE_JUDGE
#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
#else
#define gh() getchar()
#endif
#define reg register
inline ll read() {
    reg char ch = gh();
    reg ll x = 0;
    reg char t = 0;

    while (ch < '0' || ch > '9')
        t |= ch == '-', ch = gh();

    while (ch >= '0' && ch <= '9')
        x = x * 10 + (ch ^ 48), ch = gh();

    return t ? -x : x;
}
inline void putc(char ch) {
    out[len++] = ch;
}
template<class T>
inline void write(T x) {
    if (x < 0)
        putc('-'), x = -x;

    if (x > 9)
        write(x / 10);

    out[len++] = x % 10 + 48;
}
inline void flush() {
    fwrite(out, 1, len, stdout);
    len = 0;
}
inline char getc() {
    char ch = gh();

    while (ch < 'A' || ch > 'Z')
        ch = gh();

    return ch;
}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::getc;
using IO::putc;
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
using node = array<ll, 3>;
const int N = 2e5 + 10;
int n, q;
ll v;
vector<node>a[N];
struct TopTree {
    int cnt, rt, siz[N], son[N], pos[N], ppos[N], fa[N];
    struct Data {
        int sz;
        ll f[2][2];//上界点/下界点
        inline ll *operator[](int x) {
            return f[x];
        }
        inline friend Data operator*(Data A, Data B) { //Compess A<-B
            Data C;
            C.sz = A.sz + B.sz;
            C[0][0] = max({A[0][0], B[0][0], A[0][1] + B[1][0]});
            C[0][1] = max(B[0][1], A[0][1] + B[1][1]);
            C[1][0] = max(A[1][0], A[1][1] + B[1][0]);
            C[1][1] = A[1][1] + B[1][1];
            return C;
        }
        inline friend Data operator+(Data A, Data B) { //Rake A<-B
            Data C;
            C.sz = A.sz + B.sz;
            C[0][0] = max({A[0][0], B[0][0], A[1][0] + max(B[1][0], B[1][1])});
            C[0][1] = max(A[0][1], A[1][1] + max(B[1][0], B[1][1]));
            C[1][0] = max({A[1][0], B[1][0], B[1][1]});
            C[1][1] = A[1][1];
            return C;
        }
    };
#define ls tr[rt].lson
#define rs tr[rt].rson
    struct node {
        int fa, lson, rson, op;
        Data v;
    } tr[N];
    inline void pushup(int rt) {
        if (tr[rt].op == 1)
            tr[rt].v = tr[ls].v * tr[rs].v;

        if (tr[rt].op == 2)
            tr[rt].v = tr[ls].v + tr[rs].v;
    }
    inline Data newdata(ll w) {
        Data A;
        A.sz = 1;
        A[0][0] = A[1][0] = A[1][0] = A[1][1] = w;
        return A;
    }
    inline int newnode(ll w) {
        int rt = ++cnt;
        tr[rt].v = newdata(w), tr[rt].op = 0;
        ls = rs = tr[rt].fa = 0;
        return rt;
    }
    inline int newnode(int lp, int rp, int op) {
        int rt = ++cnt;
        tr[rt].op = op, ls = lp, rs = rp;
        tr[lp].fa = tr[rp].fa = rt;
        return pushup(rt), rt;
    }
    inline void dfs0(int x) {
        siz[x] = 1;

        for (auto tp : a[x]) {
            int t = tp[0], id = tp[2];
            ll w = tp[1];

            if (t == fa[x])
                continue;

            ppos[id] = pos[t] = newnode(w);
            fa[t] = x, dfs0(t), siz[x] += siz[t];

            if (siz[t] > siz[son[x]])
                son[x] = t;
        }
    }
    vector<int>pc;
    inline int build(int l, int r, int op) {
        if (l == r)
            return pc[l];

        int mid = r - 1, sz = 0;

        for (int i = l; i <= r; i++)
            sz += tr[pc[i]].v.sz;

        for (int i = l, s = 0; i < r; i++) {
            s += tr[pc[i]].v.sz;

            if (s * 2 >= sz) {
                mid = i;
                break;
            }
        }

        return newnode(build(l, mid, op), build(mid + 1, r, op), op);
    }
    inline int dfs(int x) {
        vector<int>vc;

        if (pos[x])
            vc.push_back(pos[x]);

        for (int p = x; son[p]; p = son[p]) {
            vector<int>vp;

            for (auto tp : a[p]) {
                int t = tp[0];

                if (t == son[p] || t == fa[p])
                    continue;

                vp.push_back(dfs(t));
            }

            if (!vp.size())
                vc.push_back(pos[son[p]]);
            else
                pc = vp, vc.push_back(newnode(pos[son[p]], build(0, vp.size() - 1, 2), 2));
        }

        pc = vc;
        int rtp = build(0, vc.size() - 1, 1);
        return rtp;
    }
    inline void init() {
        dfs0(1), rt = dfs(1);
    }
    inline void modify(int x, ll w) {
        tr[ppos[x]].v = newdata(w);

        for (int p = tr[ppos[x]].fa; p; p = tr[p].fa)
            pushup(p);
    }
    inline ll query() {
        return max({tr[rt].v[0][0], tr[rt].v[0][1], tr[rt].v[1][0], tr[rt].v[1][1]});
    }
} T;
ll las;
int main() {
    n = read(), q = read(), v = read();

    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        ll w = read();
        a[u].push_back((node) {
            v, w, i
        });
        a[v].push_back((node) {
            u, w, i
        });
    }

    T.init();

    while (q--) {
        int x = (read() + las) % (n - 1) + 1;
        ll w = (read() + las) % v;
        T.modify(x, w);
        write(las = T.query()), putc('\n');
    }

    flush();
}

Compilation message (stderr)

diameter.cpp: In function 'long long int IO::read()':
diameter.cpp:14:14: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   14 |     reg char ch = gh();
      |              ^~
diameter.cpp:15:12: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   15 |     reg ll x = 0;
      |            ^
diameter.cpp:16:14: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   16 |     reg char t = 0;
      |              ^

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