Submission #1097894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097894		Mike_Vu	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	2744 ms	136896 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct SMT{
    int trsz;
    vector<ll> tr, lazy;
    void init(int n = 0) {
        trsz = 2;
        while (trsz < n) trsz <<= 1;
        tr.assign(trsz<<1, 0);
        lazy.assign(trsz<<1, 0);
    }
    void insval(int i, ll val) {
        tr[i+trsz-1] = val;
    }
    void build() {
        for (int i = trsz-1; i; i--) {
            tr[i] = max(tr[i<<1], tr[(i<<1)|1]);
        }
    }
    void fix(int id) {
        if (lazy[id] == 0) return;
        tr[id] += lazy[id];
        if (id < trsz) {
            lazy[id<<1] += lazy[id];
            lazy[(id<<1)|1] += lazy[id];
        }
        lazy[id] = 0;
    }
    void update(int u, int v, int l, int r, int id, ll val) {
        fix(id);
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            lazy[id] += val;
            fix(id);
            return;
        }
        int mid = (l+r)>>1;
        update(u, v, l, mid, id<<1, val);
        update(u, v, mid+1, r, (id<<1)|1, val);
        tr[id] = max(tr[id<<1], tr[(id<<1)|1]);
    }
    void update(int u, int v, ll val) {
        update(u, v, 1, trsz, 1, val);
    }
    ll query(int u, int v, int l, int r, int id) {
        fix(id);
        if (l > v || r < u) return 0;
        if (l >= u && r <= v) return tr[id];
        int mid = (l+r)>>1;
        return max(query(u, v, l, mid, id<<1), query(u, v, mid+1, r, (id<<1)|1));
    }
    ll query(int u, int v) {
        return query(u, v, 1, trsz, 1);
    }
};

struct edge{
    int u, v;
    ll w;
    edge(int _u, int _v, ll _w) {
        u = _u;
        v = _v;
        w = _w;
    }
};

const int maxn = 1e5+5, lg = 20;
int n, q;
vector<pair<int, ll>> adj[maxn];
vector<edge> edges;
ll lim, lasans = 0;
ll dis[maxn];
SMT tr[maxn];
multiset<ll, greater<ll>> alldiam, curans[maxn];
int cenpar[maxn], sz[maxn], tin[lg][maxn], tout[lg][maxn], sztr[maxn], up[lg][maxn], timer, curcen;
int depth[maxn];

void dfs_sz(int u, int p) {
    sz[u] = 1;
    for (int i = 0; i < (int)adj[u].size(); i++) {
        int v = adj[u][i].fi;
        if (v == p || depth[v]) continue;
        dfs_sz(v, u);
        sz[u] += sz[v];
    }
}
int fcen(int u, int p, int cursz) {
    for (int i = 0; i < (int)adj[u].size(); i++) {
        int v = adj[u][i].fi;
        if (v == p || depth[v]) continue;
        if (sz[v] > (cursz>>1)) return fcen(v, u, cursz);
    }
    return u;
}

void dfs_pre(int u, int p, int layer, int las) {
    tin[layer][u] = ++timer;
    tr[curcen].insval(tin[layer][u], dis[u]);
    up[layer][u] = las;
    for (int i = 0; i < (int)adj[u].size(); i++) {
        int v = adj[u][i].fi;
        ll w = adj[u][i].se;
        if (v == p || depth[v]) continue;
        dis[v] = dis[u] + w;
        dfs_pre(v, u, layer, las == -1 ? v : las);
    }
    tout[layer][u] = timer;
}

void decompose(int u, int layer, int p) {
    //find centroid
    dfs_sz(u, -1);
    curcen = fcen(u, -1, sz[u]); //centroid
    sztr[curcen] = sz[u];
    u = curcen;
    cenpar[u] = p;
    //dfs_pre: tin, tout, init
    timer = 0;
    tr[u].init(sztr[u]);
    dis[u] = 0;
    dfs_pre(u, -1, layer, -1);
    tr[u].build();
    //for all child of cen: check diam -> multiset
    curans[u].insert(0);
    for (int i = 0; i < (int)adj[u].size(); i++) {
        int v = adj[u][i].fi;
        if (depth[v]) continue;
        ll val = tr[u].query(tin[layer][v], tout[layer][v]);
        curans[u].insert(val);
    }
    if (curans[u].size() > 1) alldiam.insert(*curans[u].begin()+*next(curans[u].begin())); //change to multiset
    //continue decompose
    depth[u] = layer;
    for (int i = 0; i < (int)adj[u].size(); i++) {
        int v = adj[u][i].fi;
        if (depth[v]) continue;
        decompose(v, layer+1, u);
    }
}

void solvequery(int u, int v, ll val) {
    //move until reach -1
    int cen = depth[u] < depth[v] ? u : v;
    int layer = depth[cen];
    while (layer > 0) {
//        cout << cen << ' ' << layer << endl;
//        system("pause");
        if (tin[layer][u] < tin[layer][v]) swap(u, v);
        int near = up[layer][u];
        ll valbef = tr[cen].query(tin[layer][near], tout[layer][near]);
        //update new w in smt
        tr[cen].update(tin[layer][u], tout[layer][u], val);
        ll valnew = tr[cen].query(tin[layer][near], tout[layer][near]);
        //check new diam -> multiset (remove, add)
        if (valbef != valnew) {
            ll befall = *curans[cen].begin()+*next(curans[cen].begin());
            curans[cen].erase(curans[cen].find(valbef));
            curans[cen].insert(valnew);
            ll newall = *curans[cen].begin()+*next(curans[cen].begin());
            if (befall != newall){
                alldiam.erase(alldiam.find(befall));
                alldiam.insert(newall);
            }
        }
        //nxt
        --layer;
        cen = cenpar[cen];
    }
    //cout with lasans
    lasans = *alldiam.begin();
    cout << lasans << "\n";
//    system("pause");
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> n >> q >> lim;
    for (int i = 0; i < n-1; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        edges.push_back(edge(u, v, w));
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    //decompose
    memset(depth, 0, sizeof(depth));
    alldiam.insert(0);
    decompose(1, 1, -1);
//    cout << "finish decompose" << endl;
//    system("pause");
    //solvequery
    while (q--){
        int id;
        ll val;
        cin >> id >> val;
        id = (lasans%(n-1)+id)%(n-1);
        val = (lasans%lim+val)%lim;
        solvequery(edges[id].u, edges[id].v, val-edges[id].w); //delta
//        cout << id << ' ' << val << endl;
        edges[id].w = val;
//        system("pause");
    }
}
/*
4 3 2000
1 2 100
2 3 1000
2 4 1000
2 1030
1 1020
1 890
2030
2080
2050

10 2 10000
1 9 1241
5 6 1630
10 5 1630
2 6 853
10 1 511
5 3 760
8 3 1076
4 10 1483
7 10 40
8 2051
5 6294
6164
7812

10 10 10000
1 9 1241
5 6 1630
10 5 1630
2 6 853
10 1 511
5 3 760
8 3 1076
4 10 1483
7 10 40
8 2051
5 6294
5 4168
7 1861
0 5244
6 5156
3 3001
8 5267
5 3102
8 3623
6164
7812
8385
6737
6738
7205
6641
7062
6581
5155
*/

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