Submission #1023363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023363		Boomyday	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	4436 ms	340616 KiB

diameter

//
// Created by adavy on 7/14/2024.
//
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define int ll



int INF = 1e18;

vector<vector<pair<int,int>>> adj; // (next,  id))
vector<vector<int>> my_trees; // edges
vector<int> w;
vector<bool> vis; // for centroid decomposition
multiset<int,greater<int>> anses;




struct segtree{
    int sz = 1;
    vector<int> seg,lz;

    void init(int n){
        while (sz < n) sz *= 2;
        seg.resize(2*sz,0);
        lz.resize(2*sz,0);
    }

    // range adds and maximums
    void pushdown(int rt, int tl, int tr){
        seg[rt] += lz[rt];
        if (tl != tr){
            lz[2*rt] += lz[rt];
            lz[2*rt+1] += lz[rt];
        }
        lz[rt] = 0;
    }
    void add(int x, int l, int r, int rt, int tl, int tr){
        pushdown(rt,tl,tr);
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            lz[rt] += x;
            pushdown(rt,tl,tr);
            return;
        }
        int tm = (tl+tr)/2;
        add(x,l,r,2*rt,tl,tm);
        add(x,l,r,2*rt+1,tm+1,tr);
        seg[rt] = max(seg[2*rt],seg[2*rt+1]);
    }
    int query(int l, int r, int rt, int tl, int tr){
        pushdown(rt,tl,tr);
        if (l > tr || r < tl) return -INF;
        if (l <= tl && tr <= r) return seg[rt];
        int tm = (tl+tr)/2;
        return max(query(l,r,2*rt,tl,tm),query(l,r,2*rt+1,tm+1,tr));
    }
};

struct tree{
    unordered_map<int,int> edge_to_node; // edge,node
    unordered_map<int,int> node_to_group;
    vector<int> group_rep,group_wt,group_set;
    int T=0,G=0;
    int name = 0;
    vector<int> ton,toff; // ton = the node number
    segtree st;
    multiset<int,greater<int>> group_vals;
    set<int> is_leader;
    int my_max = 0;

    void dfs(int u, int p){
        //if (vis[u]) assert(false);

        int cur_name = T;

        ton.push_back(T++); toff.push_back(-1);

        for (auto&[v,i]:adj[u]) if (v != p && !vis[v]){
                my_trees[i].push_back(name);

                int my_name = T;
                if (u == name){
                    group_rep.push_back(T);
                    group_wt.push_back(w[i]);
                    is_leader.insert(T);

                }



                node_to_group[T] = G;
                edge_to_node[i] = my_name;
                dfs(v,u);
                if (u == name){
                    G++;
                }

            }
        toff[cur_name] = T;
    }

    void update_edge(int e, int w_change){
        anses.erase(anses.find(my_max));
        int nd = edge_to_node[e];
        int gp = node_to_group[nd];
        group_vals.erase(group_vals.find(group_set[gp]));

        if (is_leader.count(nd)){
            group_wt[gp] += w_change;
        }
        else {
            st.add(w_change,ton[nd],toff[nd]-1,1,0,st.sz-1);
        }


        int new_max = group_wt[gp] + st.query(ton[group_rep[gp]],toff[group_rep[gp]]-1,1,0,st.sz-1);
        group_vals.insert(new_max);
        group_set[gp] = new_max;
        // now, get the maximum two elements from the multiset

        my_max = gmx();
        anses.insert(my_max);





    }

    int gmx(){
        int mx1=0,mx2=0;
        if (G==1){
            mx1 = *group_vals.begin();
        }
        else if (G >= 2){
            mx1 = *group_vals.begin();
            mx2 = *next(group_vals.begin());
        }
        return mx1 + mx2;

    }
    void init(int rt){
        name = rt;
        dfs(rt,-1);
        st.init(T+1);  // check!!!
        for (auto& [e,n]:edge_to_node){

            if (!is_leader.count(n)){
                st.add(w[e],ton[n],toff[n]-1,1,0,st.sz-1);
            }
        }
        for(int g=0;g<G;++g){
            group_set.push_back(group_wt[g] + st.query(ton[group_rep[g]],toff[group_rep[g]]-1,1,0,st.sz-1));
            group_vals.insert(group_set[g]);

        }
        // output edge to node
        my_max = gmx();
        anses.insert(my_max);

    }
};

vector<tree> trees;
vector<int> n_sz;

void init_sz(int u, int p){
    n_sz[u] = 1;
    for(auto&[v,i]:adj[u]) if (v != p && !vis[v]){
            init_sz(v,u);
            n_sz[u] += n_sz[v];
        }
}

int find_centroid(int u, int p, int n){
    for(auto&[v,i]:adj[u]) if (v != p && !vis[v]){
            if (n_sz[v] > n/2) return find_centroid(v,u,n);
        }
    return u;
}


void centroid_decomp(int u){
    init_sz(u,-1);
    int c = find_centroid(u,-1,n_sz[u]);
    //cout << "centroid is " << c << endl;
    trees[c].init(c);
    vis[c] = 1;

    for(auto&[v,i]:adj[c]) if (!vis[v]){
            centroid_decomp(v);
        }

}

// let's do a CENTROID DECOMPOSITION
signed main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,q,mw; cin >> n >> q >> mw;
    adj.resize(n);
    vis.resize(n,0);
    n_sz.resize(n,0);
    w.resize(n-1);
    for(int i=0;i<n-1;++i){
        int a,b,c; cin >> a >> b >> c; a--; b--;
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
        w[i] = c;
    }
    my_trees.resize(n-1);

    trees.resize(n,tree());
    centroid_decomp(0);

    // for each edge, output its' trees

    /*
    for (int i=0;i<n-1;++i){
        cout << "edge " << i ;
        for(auto&x:my_trees[i]){
            cout << " tree " << x << " ";

        }
        cout << endl;

    }*/

    int last = 0;

    for(int i=0;i<q;++i){
        int d,e; cin >> d >> e;
        int dprime = (d+last)%(n-1);
        int eprime = (e+last)%mw;
        int wchange = eprime - w[dprime];
        w[dprime] = eprime;


        for(auto&ct:my_trees[dprime]){
           trees[ct].update_edge(dprime,wchange);
        }
        last  = *anses.begin();

        cout << last << 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