Submission #780680

#	Time	Username	Problem	Language	Result	Execution time	Memory
780680		Hacv16	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	320 ms	73760 KiB

diameter

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

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")

#define int long long int

typedef long long ll;
const int MAX = 2e5 + 15;
const int INF = 0x3f3f3f3f;

int n, q, wlim, h[MAX], v[MAX], tin[MAX], tout[MAX], timer;
tuple<int, int, int> edges[MAX];
vector<pair<int, int>> adj[MAX];

struct Node{
    ll Mi, Mj, Mk, Mij, Mjk, Mijk, lzSum;

    Node(ll a = 0, ll b = 0, ll c = 0, ll d = 0, ll e = 0, ll f = 0, ll g = 0) :
        Mi(a), Mj(b), Mk(c), Mij(d), Mjk(e), Mijk(f), lzSum(g) { }

    Node operator + (Node other){
        Node ret;

        ret.Mi = max(Mi, other.Mi);
        ret.Mj = min(Mj, other.Mj);
        ret.Mk = max(Mk, other.Mk);
        ret.Mij = max({ Mij, other.Mij, Mi - 2 * other.Mj });
        ret.Mjk = max({ Mjk, other.Mjk, other.Mk - 2 * Mj });
        ret.Mijk = max({ Mijk, other.Mijk, Mij + other.Mk, Mi + other.Mjk });

        return ret;
    }

} seg[4 * MAX];

void refresh(int p, int l, int r){
    if(seg[p].lzSum == 0) return;

    int add = seg[p].lzSum; seg[p].lzSum = 0;

    seg[p].Mi += add;
    seg[p].Mj += add;
    seg[p].Mk += add;
    seg[p].Mij -= add;
    seg[p].Mjk -= add;

    if(l == r) return;
    int e = 2 * p, d = e + 1;
    seg[e].lzSum += add;
    seg[d].lzSum += add;
}

void build(int p, int l, int r){
    if(l == r){
        seg[p] = Node(v[l], v[l], v[l], -v[l], -v[l], 0, 0);
        return;
    }

    int m = (l + r) >> 1, e = 2 * p, d = e + 1;
    build(e, l, m); build(d, m + 1, r);

    seg[p] = seg[e] + seg[d];
}

void update(int a, int b, int x, int p, int l, int r){
    refresh(p, l, r);

    if(a > r || b < l) return;
    if(a <= l && r <= b){
        seg[p].lzSum += x;
        refresh(p, l, r);
        return;
    }

    int m = (l + r) >> 1, e = 2 * p, d = e + 1;
    update(a, b, x, e, l, m); update(a, b, x, d, m + 1, r);

    seg[p] = seg[e] + seg[d];
}

void dfs(int u, int p){
    tin[u] = ++timer;
    v[ tin[u] ] = h[u];

    for(auto [v, w] : adj[u]){
        if(v == p) continue;
        h[v] = h[u] + w;

        dfs(v, u);
    }

    tout[u] = ++timer;
    v[ tout[u] ] = h[p];
}

int32_t main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> q >> wlim;

    for(int i = 1; i < n; i++){
        auto &[u, v, w] = edges[i];
        cin >> u >> v >> w;
 
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    dfs(1, 1);
    build(1, 1, 2 * n);
 
    int last = 0;
 
    auto getI = [&](int i){ return (i + last) % (n - 1); };
    auto getW = [&](int w){ return (w + last) % (wlim); };
 
    while(q--){
        int i, newW; cin >> i >> newW;
        i = getI(i), newW = getW(newW);
 
        auto &[u, v, w] = edges[i + 1];
        if(tin[u] < tin[v]) swap(u, v);
        
        update(tin[u], tout[u] - 1, newW - w, 1, 1, 2 * n);
        w = newW;
 
        last = seg[1].Mijk;
        cout << last << '\n';
    }
}

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