Submission #1040587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040587		anton	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	324 ms	37060 KiB

diameter

#include<bits/stdc++.h>

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

int N, Q, W;
const int MAX_N = 1e5;

vector<unordered_map<int, int>> adj;


struct SegTree{
    int len =1;
    vector<int> lazy, tr;

    SegTree(int n){
        while(len<n){
            len*=2;
        }
        lazy.resize(2*len);
        tr.resize(2*len);
    }

    void upd(int u){
        tr[u] = max(tr[u*2], tr[u*2+1])+lazy[u];
    }
    void add(int l, int r,int v, int lt, int rt, int t){
        if(r<lt|| rt<l){
            return;
        }
        else if(l<=lt && rt<= r){
            lazy[t]+= v;
            tr[t] += v;
        }
        else {
            int mid = (lt+rt)/2;
            add(l, r, v, lt, mid, t*2);
            add(l, r, v, mid+1, rt, t*2+1);

            upd(t);
        }
    }

    int get(){
        return tr[1];
    }
};

pii get_furthest(int u, int a){

    pii res ={0, u};
    for(auto e: adj[u]){
        if(e.first!=a){
            pii de = get_furthest(e.first, u);
            de.first += e.second;
            if(de.first>res.first){
                res = de;
            }
        }
    }
    return res;
}

void euler_tour(int u, int a, vector<pii>& tour_t, int &t,vector<int>& dpth, int d, vector<bool>& leaf){
    int nb_c= 0;
    tour_t[u].first = t;
    dpth[u] = d;
    for(auto e: adj[u]){
        if(e.first!=a){
            nb_c++;
            euler_tour(e.first, u, tour_t, t, dpth, d+e.second, leaf);
        }
    }
    if(nb_c == 0){
        leaf[u] = true;
        t++;
    }
    tour_t[u].second = t;
}

void run_ez(){

}
signed main(){
    cin>>N>>Q>>W;
    adj.resize(N);

    vector<pii> edges;

    for(int i = 0; i<N-1; i++){
        int a, b, c;
        cin>>a>>b>>c;
        a--;b--;
        adj[a][b] = c;
        adj[b][a] = c;

        edges.push_back({a, b});
    }

    int root =0;
    
    vector<pii> tour_t(N);
    vector<int> dpth(N);
    vector<bool> leaf(N);
    int tm = 0;
    euler_tour(root, -1, tour_t, tm, dpth, 0, leaf);

    SegTree tr(N);

    for(int i = 0; i<N; i++){
        if(leaf[i]){
            tr.add(tour_t[i].first, tour_t[i].second-1, dpth[i], 0, N-1, 1);
        }
    }

    int last=  0;
    cout<<tr.get()<<endl;
    
    for(int i = 0; i<Q; i++){
        int d, e;
        cin>>d>>e;

        d = (d+last)%(N-1);
        e = (e +last)%W;

        int a = edges[d].first;
        int b=  edges[d].second;
        if(dpth[a]<dpth[b]){
            swap(a, b);
        }

        int delta = e-adj[a][b];

        adj[a][b] = e;
        adj[b][a] =e;

        tr.add(tour_t[a].first, tour_t[a].second-1,delta, 0, N-1, 1);
        cout<<tr.get()<<endl;
    }
}

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