Submission #1246331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246331		KindaGoodGames	Dynamic Diameter (CEOI19_diameter)	C++20	0 / 100	5089 ms	21848 KiB

diameter

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

int INF = numeric_limits<int>::max()/4;

struct Value{
    int ma = -INF;
    int ma2 = -INF;

    Value(){}
    Value(int a){
        ma = a; 
    }
    Value(int a, int b){
        ma = a;
        ma2 = b;
    }

    void add(int v){
        ma += v;
        ma2 += v;
    }
};

Value comb(Value a, Value b){
    vector<int> r = {a.ma,a.ma2,b.ma,b.ma2};
    sort(r.rbegin(),r.rend());
    return Value(r[0],r[1]);
}
struct SegmentTree{
    vector<Value> S;
    vector<int> lazy;
    int len = 1;

    SegmentTree(int n){
        while(len < n){
            len <<= 1;
        }

        S.resize(2*len); 
        lazy.resize(2*len); 
    }

    void upd(int i, int v){
        i += len;
        
        S[i] = Value(v);

        for(i /= 2; i > 0; i /= 2){
            S[i] = comb(S[i*2], S[i*2+1]);
        }
    }

    void apply1(int i, int v){
        S[i].add(v);
        lazy[i] += v;
    }

    void push(int i){
        apply1(i*2+1, lazy[i]);
        apply1(i*2, lazy[i]);

        lazy[i] = 0;
    }


    Value query(int ql, int qr, int l = 0, int r = -2, int i = 1){
        if(r == -2) r = len;

        if(ql <= l && r <= qr) {
            return S[i];
        }
        if(r <= ql || qr <= l) {
            return Value();
        }

        int mid = (l+r)/2;

        push(i);
        Value a = query(ql,qr,l,mid,i*2);
        Value b=  query(ql,qr,mid,r,i*2+1);
        return comb(a,b);
    }

    
    void apply(int ql, int qr, int v, int l = 0, int r = -2, int i = 1){
        if(r == -2) r = len;

        if(ql <= l && r <= qr) {
            apply1(i,v);
            return;
        }
        if(r <= ql || qr <= l) return;

        int mid = (l+r)/2;

        push(i);
        apply(ql,qr,v,l,mid,i*2);apply(ql,qr,v,mid,r,i*2+1);
        S[i] = comb(S[i*2], S[i*2+1]);
    }
};

vector<int> val, cost;
vector<int> par, sz, depth;
vector<int> start, stop;
vector<vector<pii>> adj;
int timer = 0;

void DFS(int v, int p, int d = 0, int len = 0){
    start[v] = timer++;

    depth[v] = d;
    sz[v] = 1;
    par[v] = p;

    int h = -1;
    int s = -1;
    for(auto u : adj[v]){
        if(u.first == p) continue;
        val[u.first] = len+u.second;
        cost[u.first] = u.second;
        DFS(u.first,v, d+1, len+u.second);
        
        sz[v] += sz[u.first]; 
    } 

    stop[v] = timer;
} 

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q,w;
    cin >> n >> q >> w;

    vector<tiii> edges(n-1);
    adj.resize(n);
    val.resize(n);
    par = sz = val = depth = cost=start=stop= vector<int>(n,-1);

    for(int i = 0; i < n-1; i++){
        int a,b,c;
        cin >> a >> b >> c;
        a--;b--;
        edges[i] = {a,b,c};
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    DFS(0,0);  
    val[0] = 0;
    cost[0] = 0;

    SegmentTree seg(n);

    for(int i = 0; i < n; i++){
        seg.upd(i,val[i]);
    }
    
    int last = 0;
    while(q--){
        int d,e;
        cin >> d >> e;
    
        int edge = (last+d) % (n-1);
        int weight = (e+last)%w;

        int a,b,c;
        tie(a,b,c) = edges[edge];
        if(depth[a] < depth[b]) swap(a,b);
        int diff = weight-c;

        seg.apply(start[a], stop[a], diff);

        edges[d] = {a,b,weight};
        cost[a] = weight;

        int ma = 0;
        for(int i = 0; i < n; i++){
            Value res = Value();
            
            for(auto u : adj[i]){
                if(u.first == par[i]) continue;
                Value v = seg.query(start[u.first],stop[u.first]);

                res = comb(res, Value(v.ma));
            }
            int rem = seg.query(start[i], start[i]+1).ma;
            ma = max({ma, (res.ma+res.ma2) - (2*rem),res.ma - rem});
        }

        cout << ma << "\n";
        last = ma;
    }
}

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