Submission #1040755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040755		anton	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	508 ms	40320 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;
vector<int> group;

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

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

    void upd(int u){
        vector<pii> candidats;
        for(auto e: tr[u*2]){
            candidats.push_back(e);
        }
        for(auto e: tr[u*2+1]){
            candidats.push_back(e);
        }

        sort(candidats.begin(), candidats.end());
        reverse(candidats.begin(), candidats.end());

        tr[u].clear();
        for(auto e: candidats){
            if(tr[u].size() ==2){
                break;
            }
            if(tr[u].size() == 0 || tr[u].back().second != e.second){
                tr[u].push_back(e);
            }
        }

        for(pii& e: tr[u]){
            e.first += lazy[u];
        }
    }

    void insert(int id,int gid,  int v, int lt, int rt, int t){
        if(lt==rt){
            tr[t].push_back({v, gid});
        }
        else{
            int mid =(lt+rt)/2;

            if(id<=mid){
                insert(id, gid, v, lt, mid, t*2);
            }
            else{
                insert(id, gid, v, mid+1, rt, t*2+1);
            }
            upd(t);
        }


    }
    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;
            for(pii& e: tr[t]){
                e.first +=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(){
        int res = tr[1][0].first;
        if(tr[1].size()>1){
            res += tr[1][1].first;
        }
        return res;
    }
};

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 group_dfs(int u, int a, int gid){
    group[u] = gid;
    for(auto e: adj[u]){
        if(e.first != a){
            group_dfs(e.first, u, gid);
        }
    }
}
signed main(){
    cin>>N>>Q>>W;
    adj.resize(N);
    group.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);

    int cg= 1;
    for(auto e: adj[root]){
        group_dfs(e.first, root, cg);
        cg++;
    }

    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);    
            tr.insert(tour_t[i].first,group[i], dpth[i], 0, N-1, 1);
        }
    }

    int last=  0;
    
    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;

        //cout<<a<<" delta "<<delta<<endl;

        tr.add(tour_t[a].first, tour_t[a].second-1,delta, 0, N-1, 1);
        int last = tr.get();
        cout<<last<<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