oj.uz

Submission #556692

# Submission time Handle Problem Language Result Execution time Memory
556692 2022-05-03T16:54:54 Z fatemetmhr Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 830 ms 70836 KB 
// ~~ 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){
            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]);
    }

    inline pair<ll, int> get_max(int l, int r, int lq, int rq, int v){
        if(rq <= l || r <= lq)
            return {-inf, 0};
        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 = 0, 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);
        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';
    }
}

/*
10 1 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
*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Incorrect 6 ms 15272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Incorrect 6 ms 15272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 9 ms 15208 KB Output is correct
3 Correct 10 ms 15224 KB Output is correct
4 Correct 19 ms 15444 KB Output is correct
5 Correct 67 ms 16464 KB Output is correct
6 Correct 8 ms 15188 KB Output is correct
7 Correct 7 ms 15316 KB Output is correct
8 Correct 7 ms 15344 KB Output is correct
9 Correct 9 ms 15316 KB Output is correct
10 Correct 27 ms 15628 KB Output is correct
11 Correct 109 ms 16624 KB Output is correct
12 Correct 9 ms 16116 KB Output is correct
13 Correct 10 ms 16212 KB Output is correct
14 Correct 12 ms 16296 KB Output is correct
15 Correct 38 ms 16516 KB Output is correct
16 Correct 141 ms 17776 KB Output is correct
17 Correct 44 ms 30688 KB Output is correct
18 Correct 44 ms 31436 KB Output is correct
19 Correct 53 ms 33336 KB Output is correct
20 Correct 97 ms 33856 KB Output is correct
21 Correct 227 ms 35172 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 15476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 39904 KB Output is correct
2 Correct 818 ms 39736 KB Output is correct
3 Correct 783 ms 39852 KB Output is correct
4 Correct 771 ms 39660 KB Output is correct
5 Correct 830 ms 39248 KB Output is correct
6 Correct 629 ms 37712 KB Output is correct
7 Correct 348 ms 51464 KB Output is correct
8 Correct 521 ms 51516 KB Output is correct
9 Correct 415 ms 51528 KB Output is correct
10 Correct 382 ms 51456 KB Output is correct
11 Correct 436 ms 50516 KB Output is correct
12 Correct 317 ms 45956 KB Output is correct
13 Correct 235 ms 70712 KB Output is correct
14 Correct 318 ms 70732 KB Output is correct
15 Correct 276 ms 70836 KB Output is correct
16 Correct 297 ms 70488 KB Output is correct
17 Correct 285 ms 67280 KB Output is correct
18 Correct 212 ms 52836 KB Output is correct
19 Correct 268 ms 70664 KB Output is correct
20 Correct 249 ms 70756 KB Output is correct
21 Correct 281 ms 70820 KB Output is correct
22 Correct 290 ms 70496 KB Output is correct
23 Correct 289 ms 67328 KB Output is correct
24 Correct 228 ms 52880 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Incorrect 6 ms 15272 KB Output isn't correct
3 Halted 0 ms 0 KB -