Submission #1305245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305245		khoavn2008	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	307 ms	43732 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(int i = 0, _r = (r); i < _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define size(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

const ll MOD = 1e9 + 7, N = 2e5 + 10, LOG = 19;
struct Node{
    // a = f[x]
    // b = -2f[y]
    // c = f[x] - 2f[y]
    // d = -2f[y] + f[z]
    // e = f[x] - 2f[y] + f[z]
    ll a = 0,b = 0,c = 0,d = 0,e = 0;
};
int n,q;
ll W, ew[N];
pair<int,int> edge[N];
vector<int> adj[N];
int t,tin[N],tout[N],tour[N];
void dfs(int u,int p = -1){
    tin[u] = ++t;
    tour[t] = u;
    for(int v : adj[u])if(v != p){
        dfs(v, u);
        tour[++t] = u;
    }
    tout[u] = t;
}
Node st[N * 4];
ll lz[N * 4];
void apply(int c,ll val){
    st[c].a += val;
    st[c].b -= val * 2;
    st[c].c -= val;
    st[c].d -= val;
    lz[c] += val;
}
void push(int c,int l,int r){
    if(!lz[c])return;
    apply(l, lz[c]);
    apply(r, lz[c]);
    lz[c] = 0;
}
Node merge(Node l, Node r){
    Node res;
    res.a = max(l.a, r.a);
    res.b = max(l.b, r.b);
    res.c = max({l.c, r.c, l.a + r.b});
    res.d = max({l.d, r.d, l.b + r.a});
    res.e = max({l.e, r.e, max(l.a + r.d, l.c + r.a)});
    return res;
}
void update(int u,int v,ll val,int id = 1,int l = 1,int r = t){
    if(v < l || r < u)return;
    if(u <= l && r <= v){
        apply(id, val);
        return;
    }
    int mid = (l + r) >> 1;
    push(id, id << 1, id << 1 | 1);
    update(u, v, val, id << 1, l, mid);
    update(u, v, val, id << 1 | 1, mid + 1, r);
    st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
int main(){
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q>>W;
    FOR(i,1,n - 1){
        int u,v;
        cin>>u>>v>>ew[i];
        adj[u].pb(v);
        adj[v].pb(u);
        edge[i] = {u, v};
    }
    dfs(1);
    FOR(i,1,n - 1){
        if(tin[edge[i].fi] > tin[edge[i].se])swap(edge[i].fi, edge[i].se);
        update(tin[edge[i].se], tout[edge[i].se], ew[i]);
    }
    ll last = 0;
    while(q--){
        ll d,e;cin>>d>>e;
        d = (d + last) % (n - 1);
        e = (e + last) % W;
        update(tin[edge[d + 1].se], tout[edge[d + 1].se], e - ew[d + 1]);
        ew[d + 1] = e;
        cout<<(last = st[1].e)<<endl;
    }
}

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