Submission #557314

#	Time	Username	Problem	Language	Result	Execution time	Memory
557314		fatemetmhr	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	1131 ms	70956 KiB

diameter

// ~~ Be name khoda ~~ //
 
#include <bits/stdc++.h>
 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
 
using namespace std;
 
typedef long long ll;
 
#define all(x)    x.begin(), x.end()
#define fi        first
#define se        second
#define pb        push_back
 
const int maxn5 = 1e5 + 10;
const int maxnt = 4e5 + 10;
const ll  inf   = 2e18;
 
 
struct segment_tree{
 
    ll val[maxn5], lazy[maxnt];
    pair <ll, int> mx[maxnt];
 
    inline void build(int l, int r, int v){
        if(r - l == 1){
            mx[v] = {val[l], l};
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, v * 2);
        build(mid, r, v * 2 + 1);
        mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
    }
 
    inline void add(int l, int r, int lq, int rq, ll valu, int v){
        if(rq <= l || r <= lq)
            return;
        if(lq <= l && r <= rq){
            lazy[v] += valu;
            mx[v].fi += valu;
            return;
        }
        int mid = (l + r) >> 1;
        add(l, mid, lq, rq, valu, v * 2);
        add(mid, r, lq, rq, valu, v * 2 + 1);
        mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
        mx[v].fi += lazy[v];
    }
 
    inline void update(int l, int r, int id, ll valu, int v){
        if(r - l == 1){
            lazy[v] = 0;
            val[l] = valu;
            mx[v] = {valu, l};
            //cout << "update for " << l << ' ' << valu << endl;
            return;
        }
        int mid = (l + r) >> 1;
        if(id < mid)
            update(l, mid, id, valu - lazy[v], v * 2);
        else
            update(mid, r, id, valu - lazy[v], v * 2 + 1);
        mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
        mx[v].fi += lazy[v];
    }
 
    inline pair<ll, int> get_max(int l, int r, int lq, int rq, int v){
        if(rq <= l || r <= lq)
            return {-inf, 0};
        //cout << "seeing futrure " << l << ' ' << r << ' ' << lq << ' '<< rq << ' ' << mx[v].fi << ' ' << mx[v].se << endl;
        if(lq <= l && r <= rq)
            return mx[v];
        int mid = (l + r) >> 1;
        auto ans = max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1));
        //cout << "hey see this " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << ans.fi << ' ' << ans.se << ' ' << lazy[v] << endl;
        return {ans.fi + lazy[v], ans.se};
    }
 
 
} fut_seg, hld_seg;
 
int ti = -1, st[maxn5], ft[maxn5], pos = -1, n;
int id[maxn5], big[maxn5], sz[maxn5], top[maxn5], ver[maxn5];
int h[maxn5], f[maxn5], a[maxn5], b[maxn5], retuid[maxn5];
ll hw[maxn5], mxw[maxn5], paredge[maxn5], c[maxn5];
vector <pair<int, ll>> adj[maxn5];
 
inline void dfs_det(int v, int par){
    sz[v] = 1;
    big[v] = -1;
    st[v] = ++ti;
    ver[ti] = v;
    mxw[v] = 0;
    for(auto [u, c] : adj[v]) if(u != par){
        h[u] = h[v] + 1;
        hw[u] = hw[v] + c;
        paredge[u] = c;
        dfs_det(u, v);
        sz[v] += sz[u];
        mxw[v] = max(mxw[v], mxw[u] + c);
        if(big[v] == -1 || sz[big[v]] <= sz[u])
            big[v] = u;
    }
    ft[v] = ti;
    return;
}
 
inline void dfs_hld(int v, int par){
    id[v] = ++pos;
    if(big[v] != -1){
        top[big[v]] = top[v];
        f[big[v]] = f[v];
        dfs_hld(big[v], v);
    }
    ll val = 0;
    for(auto [u, c] : adj[v]) if(u != big[v] && u != par){
        f[u] = v;
        top[u] = u;
        val = max(val, (mxw[u] + c));
        dfs_hld(u, v);
    }
    //cout << "ok " << v << ' ' << id[v] << ' ' << val << ' ' << hw[v]  << endl;
    hld_seg.val[id[v]] = val - hw[v];
    retuid[v] = pos;
    return;
}
 
inline void update(int v, int u){
    if(v == -1)
        return;
    if(u != big[v]){
        //cout << "in case of " << v << ' ' << u << ' ' << st[v] << ' ' << ft[v] << ' ' << st[u] << ' ' << ft[u] << ' ' << st[big[v]] << ' '<< ft[big[v]] << endl;
        ll val = fut_seg.get_max(0, n, st[v], st[big[v]], 1).fi;
        //cout << "a " << val << endl;
        val = max(val, fut_seg.get_max(0, n, ft[big[v]] + 1, ft[v] + 1, 1).fi);
        hld_seg.update(0, n, id[v], val - 2 * fut_seg.get_max(0, n, st[v], st[v] + 1, 1).fi, 1);
        //cout << "with final value " << val << ' ' << id[v] << ' ' << big[v] << ' ' << fut_seg.get_max(0, n, st[v], st[v] + 1, 1).fi << endl;
        //cout << "done " << endl;
    }
    update(f[v], top[v]);
}
 
inline ll get(int v){
    //cout << "all about getting " << v << ' ' << f[v] << ' ' << top[v] << endl;
    auto tmp = hld_seg.get_max(0, n, id[top[v]], id[v], 1);
    ll res = tmp.fi;
    //cout << tmp.se << endl;
    //cout << res << endl;
    if(f[v] == -1)
        return res;
    res = max(res, get(f[v]));
    int u = top[v];
    int z = f[v];
    ll ezafe = fut_seg.get_max(0, n, st[z], st[z] + 1, 1).fi;
    ezafe *= 2;
    res = max(res, fut_seg.get_max(0, n, st[z], st[u], 1).fi - ezafe);
    res = max(res, fut_seg.get_max(0, n, ft[u] + 1, ft[z] + 1, 1).fi - ezafe);
    //cout << "returning " << res << endl;
    return res;
}
 
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    ll w;
    int q; cin >> n >> q >> w;
 
    for(int i = 0; i < n - 1; i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        adj[a[i]].pb({b[i], c[i]});
        adj[b[i]].pb({a[i], c[i]});
    }
 
    f[0] = -1;
    top[0] = 0;
    dfs_det(0, -1);
    dfs_hld(0, -1);
    for(int i = 0; i < n; i++)
        fut_seg.val[st[i]] = hw[i];
    fut_seg.build(0, n, 1);
    hld_seg.build(0, n, 1);
 
    //cout << "avale kar " << fut_seg.get_max(0, n, st[9], st[big[9]], 1).fi << endl;
 
    ll last = 0;
    for(int i = 0; i < q; i++){
        ll d, e; cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;
        //cout << "________________query " << d << ' ' << e << endl;
        if(st[a[d]] > st[b[d]])
            swap(a[d], b[d]);
        // a pedar hast
        fut_seg.add(0, n, st[b[d]], ft[b[d]] + 1, e - c[d], 1);
        //cout << "befor update " << endl;
        //cout << "idea of " << st[b[d]] << ' ' << ft[b[d]] << ' ' << b[d] << ' ' << e- c[d] << endl;
        //cout << "max is " << fut_seg.get_max(0, n, st[5], ft[5] + 1, 1).fi << endl;
        update(a[d], b[d]);
        hld_seg.add(0, n, id[b[d]], retuid[b[d]] + 1, -e + c[d], 1);
        //cout << "every time check " << hld_seg.get_max(0, n, id[1], id[1] + 1, 1).fi << endl;
        //cout << "while having " << b[d] << ' ' << id[b[d]] << ' ' << retuid[b[d]] << ' ' << -e + c[d] << endl; 
        auto tmp = fut_seg.mx[1];
        int v = ver[tmp.se];
        //cout << "found " << v << ' ' << tmp.fi << endl;
        last = tmp.fi + get(v);
        //cout << "oh! " << last << endl;
        last = max(last, tmp.fi);
        c[d] = e;
        cout << last << '\n';
    }
}

/*
7 8 16
2 1 9
3 2 3
4 1 11
5 4 15
6 1 4
7 5 7
2 0
4 6
1 6
1 1
5 14
3 13
4 11
1 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