Submission #1101564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101564		underwaterkillerwhale	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3497 ms	237088 KiB

diameter

//#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e5 + 7;
int Mod = 1e9 + 7;///lon
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 450;

int n, Q;
ll mxW;
vector<pll> ke[N];
vector<pii> edges = {MP(0, 0)}; ///1-indxed

int cpar[N], del[N], szC[N];
ll Wp[N], high[N];

struct Centroid {
    struct Segment_Tree {
        int m;
        vector<pll> st;
        vector<ll> lz;

        void build (int id, int l, int r) {
            if (l == r) {
                st[id] = MP(0, l);
                return;
            }
            int mid = l + r >> 1;
            build (id << 1, l, mid);
            build (id << 1 | 1, mid + 1, r);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }

        void init (int n) {
            m = n;
            st.resize ((m << 2) + 1);
            lz.resize ((m << 2) + 1);
            build (1, 1, m);
        }

        inline void down (int id) {
            rep (i, id << 1, id << 1 | 1) {
                st[i].fs += lz[id];
                lz[i] += lz[id];
            }
            lz[id] = 0;
        }

        void update (int id, int l, int r, int u, int v, ll D) {
            if (l > v || r < u) return;
            if (l >= u && r <= v) {
                st[id].fs += D;
                lz[id] += D;
                return;
            }
            int mid = l + r >> 1;
            down(id);
            update (id << 1, l, mid, u, v, D);
            update (id << 1 | 1, mid + 1, r, u, v, D);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }

        pll get (int id, int l, int r, int u, int v) {
            if (l > v || r < u || u > v) return MP(0, 0);
            if (l >= u && r <= v) return st[id];
            int mid = l + r >> 1;
            down(id);
            return max(get (id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
        }

        void update (int u, int v, ll D) {
            update (1, 1, m, u, v, D);
        }

        pll get (int u, int v) {
            return get (1, 1, m, u, v);
        }
        ll getD (int u) {
            return get (1, 1, m, u, u).fs;
        }
    }ST; ///segtree theo euler tour

    int m, Croot;
    vector<int> nodes, ein, eout, anc, eul; ///anc theo lab

    int Lab (int X) {
        int pos = lower_bound(ALL(nodes), X) - nodes.begin();
        if (nodes[pos] != X) return -1;
        return pos;
    }

    void init (int u, int sz) {
        Croot = u;
        m = sz;

        nodes = {0}; ///1-indexed
        ein.resize(m + 1);
        eout.resize(m + 1);
        eul.resize(m + 1);
        anc.resize(m + 1);

        function<void(int, int)> pdfs = [&] (int u, int p) {
            nodes.pb(u);
            iter (&id, ke[u]) {
                ll v, w;
                tie(v, w) = id;
                if (!del[v] && v != p) pdfs(v, u);
            }
        };
        pdfs(Croot, 0);
        sort (ALL(nodes));
        ST.init(m);

        int time_dfs = 0;
        function<void(int, int, int)> dfs = [&] (int u, int p, int Anc) {
            int cur = Lab(u);
            anc[cur] = Anc;
            ein[cur] = ++time_dfs;
            eul[time_dfs] = cur;
            iter (&id, ke[u]) {
                ll v, w;
                tie(v, w) = id;
                if (!del[v] && v != p) {
                    if (p == 0) dfs(v, u, Lab(v));
                    else dfs(v, u, Anc);
                }
            }
            eout[cur] = time_dfs;
        };
        dfs(Croot, 0, 0);
    }

    void update (int u, int v, ll D) {
        u = Lab(u), v = Lab(v);
        if (u  == -1 || v == -1) return;
        if (ein[u] < ein[v])
            swap(u, v);
        ST.update(ein[u], eout[u], D);
    }

    pll Find_max_Path (int u) { ///return Len and mxvertice of inital state not the compressed one
        u = Lab(u);
        pll res = max(ST.get(1, ein[anc[u]] - 1), ST.get(eout[anc[u]] + 1, m));
        return MP(ST.getD(ein[u]) + res.fs, nodes[eul[res.se]]);
    }
}CT[N];

void solution () {
    cin >> n >> Q >> mxW;
    rep (i, 1, n - 1) {
        ll u, v, w;
        cin >> u >> v >> w;
        ke[u].pb({v, w});
        ke[v].pb({u, w});
        edges.pb(MP(u, v));
    }
    function<void(int, int)> pdfs = [&] (int u, int p) {
        high[u] = high[p] + 1;
        iter (&id, ke[u]) {
            ll v, w;
            tie(v, w) = id;
            if (v != p) {
                Wp[v] = w;
                pdfs(v, u);
            }
        }
    };
    pdfs(1, 0);
    function<void(int, int)> cpdfs = [&] (int u, int p) {
        szC[u] = 1;
        iter (&id, ke[u]) {
            ll v, w;
            tie(v, w) = id;
            if (!del[v] && v != p) {
                cpdfs(v, u);
                szC[u] += szC[v];
            }
        }
    };
    function<int(int, int, int)> get_cen = [&] (int u, int p, int Delta) {
        iter (&id, ke[u]) {
            ll v, w;
            tie(v, w) = id;
            if (!del[v] && v != p && szC[v] > Delta)
                return get_cen (v, u, Delta);
        }
        return u;
    };
    function<void(int, int)> cen_dcps = [&] (int u, int p) {
        cpdfs(u, 0);
        int cen = get_cen (u, 0, szC[u] >> 1);
        del[cen] = 1;
        if (p != 0) cpar[cen] = p;
        CT[cen].init(cen, szC[u]);
        iter (&id, ke[cen]) {
            ll v, w;
            tie(v, w) = id;
            if (!del[v] && v != p)
                cen_dcps (v, cen);
        }
    };
    cen_dcps(1, 0);

    auto Update = [&] (int u, int v, ll Delta) {
        int ver = u;
        while (ver != 0) {
            CT[ver].update (u, v, Delta);
            ver = cpar[ver];
        }
    };

    rep (i, 1, n - 1) {
        int u, v;
        tie(u, v) = edges[i];
        if (high[u] < high[v]) swap(u, v);
        Update (u, v, Wp[u]);
    }

    function<pll(int)> get_max_Path = [&] (int X) {///dist and ver
        pll res = MP(0, X);
        int u = X;
        while (u > 0){
            res = max(CT[u].Find_max_Path(X), res);
            u = cpar[u];
        }
        return res;
    };
    auto Find_diameter = [&] () { ///dist and pair of diameter
        return get_max_Path(get_max_Path(1).se).fs;
    };

//    cout << Find_diameter() <<"\n";

    ll Ans = 0;
    rep (i, 1, Q) {
        ll D, E;
        cin >> D >> E;

        D = (D + Ans) % (n - 1) + 1;
        E = (E + Ans) % mxW;

        int u, v;
        tie(u, v) = edges[D];

        if (high[u] < high[v]) swap(u, v);
        ll Delta = E - Wp[u];
        Wp[u] = E;

        Update (u, v, Delta);

        Ans = Find_diameter();
        cout << Ans <<"\n";
    }
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +10

5 5
01101
10001
00110
10101
00100
*/

Compilation message (stderr)

diameter.cpp: In member function 'void Centroid::Segment_Tree::build(int, int, int)':
diameter.cpp:47:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |             int mid = l + r >> 1;
      |                       ~~^~~
diameter.cpp: In member function 'void Centroid::Segment_Tree::update(int, int, int, int, int, long long int)':
diameter.cpp:75:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |             int mid = l + r >> 1;
      |                       ~~^~~
diameter.cpp: In member function 'std::pair<long long int, long long int> Centroid::Segment_Tree::get(int, int, int, int, int)':
diameter.cpp:85:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |             int mid = l + r >> 1;
      |                       ~~^~~

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