Submission #290022

#	Time	Username	Problem	Language	Result	Execution time	Memory
290022		ngotienhung	Dynamic Diameter (CEOI19_diameter)	C++14	24 / 100	570 ms	69496 KiB

diameter

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back

using namespace std;

const int maxN = 1e5 + 10;
const int inf = 1e18;

struct TEdge{int u, v, w;};

int         n,q,w,v;
int         timer = 0;
int         vtx[maxN], tin[maxN], tout[maxN], a[maxN], d[maxN];
TEdge       e[maxN];
vector<int> adj[maxN];

struct Node
{
    int d1, d2, d12, d23, d123, tmp;

    void add(int t){
        d1 += t;
        d2 += t;
        d12 -= t;
        d23 -= t;
        tmp += t;
    }

    void push(Node& a, Node& b){
        a.add(tmp);
        b.add(tmp);
    }
} st[maxN * 4];

Node operator + (Node a, Node b){
    Node x;
    x.d1 = max(a.d1, b.d1);
    x.d2 = min(a.d2, b.d2);
    x.d12 = max(a.d12, max(b.d12, a.d1 - b.d2 * 2));
    x.d23 = max({a.d23, b.d23, -2 * a.d2 + b.d1});
    x.d123 = max(max(a.d123, b.d123), max(a.d12 + b.d1, a.d1 + b.d23));
    x.tmp = 0;
    return x;
}

void dfs(int u){
    tin[u] = timer;

    for(auto x : adj[u]){
        if(vtx[x] != u){
            if(e[x].u == u)
                v = e[x].v;
            else
                v = e[x].u;
            vtx[x] = v;
            d[v] = d[u] + e[x].w;
            a[timer++] = d[u];
            dfs(v);
        }
    }
    a[timer++] = d[u];
    tout[u] = timer;
}

void build(int id, int l, int r){
    if(l + 1 == r){
        st[id] = {a[l], a[l], -inf, -inf, 0, 0};
    }
    else{
        build(id << 1, l, (l + r) >> 1);
        build(id << 1 | 1, (l + r) >> 1, r);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
}

void update(int id, int l, int r, int u, int v, int d){
    if(u <= l && r <= v){
        st[id].add(d);
        return;
    }

    if(r <= u || l >= v) return;

    st[id].push(st[id << 1], st[id << 1 | 1]);
    int mid = (l + r) >> 1;
    update(id << 1, l, mid, u, v, d);
    update(id << 1 | 1, mid, r, u, v, d);
    st[id] = st[id << 1] + st[id << 1 | 1];
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(); cout.tie();
    //freopen("DD.inp", "r", stdin);

    cin >> n >> q >> w;
    for(int i = 0; i < n - 1; ++i){
        cin >> e[i].u >> e[i].v >> e[i].w;
        adj[e[i].u].pb(i);
        adj[e[i].v].pb(i);
    }

    dfs(1);
    build(1, 0, 2 * n - 1);

    int last = 0;
    for(int i = 1; i <= q; ++i){
        int x,y;
        cin >> x >> y;
        x = (x + last) % (n - 1);
        y = (y + last) % w;
        int u = vtx[x];
        update(1, 0, 2 * n - 1, tin[u], tout[u], y - e[x].w);
        e[x].w = y;
        last = max(st[1].d1, st[1].d123);
        cout << last << endl;
    }
}

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