Submission #1259261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259261		vuquangsang	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	291 ms	49756 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

#define     el "\n"
#define     FOR(i,a,b) for(int i = (a), _b = (b); i <= _b; i++)
#define     FORD(i,a,b) for(int i = (a), _b = (b); i >= _b; i--)
#define     pb push_back
#define     fi first
#define     se second
#define     all(x) x.begin(),x.end()
#define     lg(x) __lg(x)
#define     alla(a,n) a+1,a+n+1


template <class T> bool maxi(T &x, T y) { if(x < y) { x = y ; return true ;} return false;}
template <class T> bool mini(T &x, T y) { if(x > y) { x = y ; return true ;} return false;}


const int N = 2e5 + 2;

#define pii pair<int, int>
#define ll long long
#define int ll
struct Edge
{
    ll x, y, w;
} E[N];

int n, q;
ll MAX_W;
vector<pair<int, int>> adj[N];
void inp()
{
    cin >> n >> q >> MAX_W;
    FOR(i, 1, n - 1) {
        ll x, y, w;
        cin >> x >> y >> w;
        E[i] = {x, y, w};
        adj[x].pb({y, w});
        adj[y].pb({x, w});
    }
}

/*  4 months to VOI
    Try your best
    No regrets */

namespace sub1
{
    const ll INF = 1e16;

    ll Dist[N];
    int in[N], out[N], time = 0, euler[N];
    int h[N];

    void dfs(int u, int p)
    {
        in[u] = ++time;
        euler[time] = u;
        for(pair<int, int> x : adj[u]) {
            int v = x.fi, w = x.se;
            if(v == p) continue;
            Dist[v] = Dist[u] + w;
            h[v] = h[u] + 1;

            dfs(v, u);
            euler[++time] = u;
        }
        out[u] = time;
    }

    struct Node
    {
        ll mx, mn, pre, suf, ans;
    } st[8 * N];

    ll lz[8 * N];

    Node Merge(Node a, Node b)
    {
        Node res;
        res.ans = max({a.ans, b.ans, a.mx + b.suf, a.pre + b.mx, a.pre, b.suf, a.suf, b.pre});
        res.mx = max(a.mx, b.mx);
        res.mn = min(a.mn, b.mn);
        res.pre = max({a.pre, b.pre, a.mx - 2 * b.mn, - a.mn, - b.mn});
        res.suf = max({a.suf, b.suf, b.mx - 2 * a.mn, - a.mn, - b.mn});
        return res;
    }
    void build(int id, int l, int r)
    {
        if(l == r) {
            st[id] = {Dist[euler[l]], Dist[euler[l]], -INF, -INF, -INF};
            return;
        }
        int mid = (r + l) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        st[id] = Merge(st[id << 1], st[id << 1 | 1]);
    }

    void add(int id, ll val)
    {
        st[id].mx += val;
        st[id].mn += val;
        st[id].pre -= val;
        st[id].suf -= val;
        lz[id] += val;
    }
    void down(int id)
    {
        if(lz[id]) {
            ll val = lz[id];
            add(id << 1, val);
            add(id << 1 | 1, val);
            lz[id] = 0;
        }
    }
    void upd(int id, int l, int r, int u, int v, ll val)
    {
        if(r < u || v < l) return;
        if(u <= l && r <= v) {
            add(id, val);
            return;
        }
        int mid = (r + l) >> 1;
        down(id);
        upd(id << 1, l, mid, u, v, val);
        upd(id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = Merge(st[id << 1], st[id << 1 | 1]);
    }
    Node get(int id, int l, int r, int u, int v)
    {
        if(r < u || v < l) return {-INF, INF, -INF, -INF, -INF};
        if(u <= l && r <= v) return st[id];
        int mid = (r + l) >> 1;
        down(id);
        return Merge(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
    void slv()
    {
        dfs(1, 1);
        int lim = 2 * n - 1;
//        FOR(i, 1, lim) cout << euler[i] << " "; cout << el;
        build(1, 1, lim);
//        cout << get(1, 1, n, 1, n).ans;

        ll last = 0;
        ll d, val;
        while(q--) {
            cin >> d >> val;
            d = (d + last) % (n - 1);
            val = (last + val) % MAX_W;

            ll u = E[d + 1].x;
            ll v = E[d + 1].y;
            ll w = E[d + 1].w;

            ll Change = val - w;

            if(h[u] < h[v]) swap(u, v);

            upd(1, 1, lim, in[u], out[u], Change);

            E[d + 1].w = val;

            last = get(1, 1, lim, 1, lim).ans;
            cout << last << el;


        }
    }
}

/* Code slowly, think carefully */

main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    #define __Azul__ "1192B"
    if(fopen(__Azul__".inp", "r")) {
        freopen(__Azul__".inp", "r", stdin);
        freopen(__Azul__".out", "w", stdout);
    }

    bool qs = 0;

    int T = 1;
    if(qs) cin >> T;
    while(T--) {
        inp();
        sub1::slv();
    }

    cerr << "\nTime" << 0.001 * clock() << "s "; return 0;


}

Compilation message (stderr)

diameter.cpp:176:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  176 | main()
      | ^~~~
diameter.cpp: In function 'int main()':
diameter.cpp:182:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         freopen(__Azul__".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:183:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         freopen(__Azul__".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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