Submission #1093307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093307		gyg	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	827 ms	478528 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vct vector
#define pii pair<int, int>
#define fir first 
#define sec second 
#define hmap unordered_map
#define prq priority_queue
const int MX_N = 1e5 + 5;

int n, q, w;
arr<arr<int, 3>, MX_N> edg;
arr<vct<pii>, MX_N> adj; // Weights are original

arr<bool, MX_N> dltd;
arr<int, MX_N> sz;
void cmp_szs(int u, int pr = -1) {
    sz[u] = 1;
    for (pii x : adj[u]) {
        if (dltd[x.fir] || x.fir == pr) continue;
        cmp_szs(x.fir, u);
        sz[u] += sz[x.fir];
    }
}
int gt_cnt(int u, int wh_sz, int pr = -1) {
    for (pii x : adj[u]) {
        if (dltd[x.fir] || x.fir == pr) continue;
        if (2 * sz[x.fir] > wh_sz) return gt_cnt(x.fir, wh_sz, u);
    }
    return u;
}
arr<hmap<int, int>, MX_N> dpth, dst;
arr<int, MX_N> cnt_pr; // 0 for first centroid
void dfs(int u, int cnt, int pr = -1) {
    if (u != cnt) cnt_pr[u] = cnt;
    for (pii x : adj[u]) {
        if (dltd[x.fir] || x.fir == pr) continue;
        dpth[cnt][x.fir] = dpth[cnt][u] + 1, dst[cnt][x.fir] = dst[cnt][u] + x.sec;
        dfs(x.fir, cnt, u);
    }
}
void bld(int u) {
    cmp_szs(u);
    int cnt = gt_cnt(u, sz[u]);

    dpth[cnt][cnt] = 0, dst[cnt][cnt] = 0;
    dfs(cnt, cnt);

    dltd[cnt] = true;
    for (pii x : adj[cnt])
        if (!dltd[x.fir]) bld(x.fir);
}

arr<vct<int>, MX_N> chldren;
int nm_indxs;
arr<int, MX_N> st_indx, fn_indx;
void cmp_indxs(int u) {
    nm_indxs++, st_indx[u] = nm_indxs;
    for (int v : chldren[u]) cmp_indxs(v);
    fn_indx[u] = nm_indxs;
}

int cnv_indx(int u, int indx) {
    assert(st_indx[u] <= indx && indx <= fn_indx[u]);
    return indx - st_indx[u] + 1;
}
struct Nd { int mx, lzy; };
arr<vct<Nd>, MX_N> sgtr;
void prp(int i, int u) {
    sgtr[i][2 * u].mx += sgtr[i][u].lzy, sgtr[i][2 * u].lzy += sgtr[i][u].lzy;
    sgtr[i][2 * u + 1].mx += sgtr[i][u].lzy, sgtr[i][2 * u + 1].lzy += sgtr[i][u].lzy;
    sgtr[i][u].lzy = 0;
}
void upd(int i, int l, int r, int vl, int lw, int hg, int u = 1) {
    if (l > r) return;
    if (r < lw || hg < l) return;
    if (l <= lw && hg <= r) { sgtr[i][u].mx += vl, sgtr[i][u].lzy += vl; return; }
    prp(i, u);
    int md = (lw + hg) / 2;
    upd(i, l, r, vl, lw, md, 2 * u), upd(i, l, r, vl, md + 1, hg, 2 * u + 1);
    sgtr[i][u].mx = max(sgtr[i][2 * u].mx, sgtr[i][2 * u + 1].mx);
}
int qry(int i, int l, int r, int lw, int hg, int u = 1) {
    if (r < lw || hg < l) return -1;
    if (l <= lw && hg <= r) return sgtr[i][u].mx;
    prp(i, u);
    int md = (lw + hg) / 2;
    return max(qry(i, l, r, lw, md, 2 * u), qry(i, l, r, md + 1, hg, 2 * u + 1));
}

arr<set<pii>, MX_N> dsts;
set<pii> whl_dsts;
int gt_dst(int u) {
    auto it = dsts[u].rbegin();
    int ans = 0;
    for (int i = 1; i <= 2; i++) {
        if (it == dsts[u].rend()) break;
        ans += it->fir;
        it++;
    }
    return ans;
}

void prcmp() {
    bld(1);
    for (int u = 1; u <= n; u++)
        if (cnt_pr[u] != 0) chldren[cnt_pr[u]].push_back(u);
    for (int u = 1; u <= n; u++) 
        if (cnt_pr[u] == 0) { cmp_indxs(u); break; }
    
    for (int u = 1; u <= n; u++) sgtr[u].resize(4 * (fn_indx[u] - st_indx[u]) + 10);
    for (int u = 1; u <= n; u++) {
        for (pii x : dst[u]) {
            int sb_sz = fn_indx[u] - st_indx[u] + 1;
            int cnv = cnv_indx(u, st_indx[x.fir]);
            upd(u, cnv, cnv, x.sec, 1, sb_sz);
        }
    }

    for (int u = 1; u <= n; u++) {
        for (int v : chldren[u]) {
            int sb_sz = fn_indx[u] - st_indx[u] + 1;
            dsts[u].insert({qry(u, cnv_indx(u, st_indx[v]), cnv_indx(u, fn_indx[v]), 1, sb_sz), v});
        }
        whl_dsts.insert({gt_dst(u), u});
        // cout << u << ": " << gt_dst(u) << endl;
    }

    // for (int u = 1; u <= n; u++) {
    //     cout << u << " --- ";
    //     for (pii x : dst[u]) {
    //         int sb_sz = fn_indx[u] - st_indx[u] + 1;
    //         int cnv = cnv_indx(u, st_indx[x.fir]);
    //         cout << x.fir << ":" << qry(u, cnv, cnv, 1, sb_sz) << " ";
    //     }
    //     cout << endl;
    // }
}

signed main() {
    // freopen("dm.in", "r", stdin);
    cin >> n >> q >> w;
    for (int i = 1; i <= n - 1; i++) {
        cin >> edg[i][0] >> edg[i][1] >> edg[i][2];
        adj[edg[i][0]].push_back({edg[i][1], edg[i][2]});
        adj[edg[i][1]].push_back({edg[i][0], edg[i][2]});
    }

    prcmp();

    int ans = 0;
    for (int i = 1; i <= q; i++) {
        int d, e; cin >> d >> e;
        d = (d + ans) % (n - 1), e = (e + ans) % w;
        
        int u = edg[d + 1][0], v = edg[d + 1][1], dlt = e - edg[d + 1][2];
        edg[d + 1][2] = e;
        // cout << u << " " << v << " " << e << ": " << endl;
        if (st_indx[u] > st_indx[v]) swap(u, v);

        int w = v, fst_lst = -1;
        while (w != u) { fst_lst = w, w = cnt_pr[w];}

        // assert(fst_lst != -1);
        assert(st_indx[u] <= st_indx[fst_lst] && fn_indx[fst_lst] <= fn_indx[u]);

        int lst = fst_lst;
        while (w != 0) { // Maybe assert last works here?
            whl_dsts.erase({gt_dst(w), w});
            dsts[w].erase({qry(w, cnv_indx(w, st_indx[lst]), cnv_indx(w, fn_indx[lst]), 1, fn_indx[w] - st_indx[w] + 1), lst});
            if (dpth[w][u] < dpth[w][v]) {
                upd(w, cnv_indx(w, st_indx[fst_lst]), cnv_indx(w, fn_indx[fst_lst]), dlt, 1, fn_indx[w] - st_indx[w] + 1);
                // assert(st_indx[lst] <= st_indx[fst_lst] && fn_indx[fst_lst] <= fn_indx[lst]);
            } else {
                upd(w, cnv_indx(w, st_indx[u]), cnv_indx(w, st_indx[fst_lst] - 1), dlt, 1, fn_indx[w] - st_indx[w] + 1);
                upd(w, cnv_indx(w, fn_indx[fst_lst] + 1), cnv_indx(w, fn_indx[u]), dlt, 1, fn_indx[w] - st_indx[w] + 1);
            }
            // cout << qry(w, cnv_indx(w, st_indx[lst]), cnv_indx(w, fn_indx[lst]), 1, fn_indx[w] - st_indx[w] + 1) << endl;
            dsts[w].insert({qry(w, cnv_indx(w, st_indx[lst]), cnv_indx(w, fn_indx[lst]), 1, fn_indx[w] - st_indx[w] + 1), lst});
            whl_dsts.insert({gt_dst(w), w});
            lst = w, w = cnt_pr[w];
        }
        ans = whl_dsts.rbegin()->fir;
        cout << ans << endl;
    }


}

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