답안 #837795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837795	2023-08-25T17:30:58 Z	jasmin	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	2719 ms	304612 KB

diameter

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int INF=LLONG_MAX;
const int L=25;

struct segtree{ //lazy maximum segtree with add updates

    vector<int> tree;
    vector<int> lazy;

    segtree(int n){
        tree.assign(n*4, 0);
        lazy.assign(n*4, 0);
    }

    int update_node(int v, int add){
        tree[v] += add;
        lazy[v] += add;

        return tree[v];
    }

    void propagate(int l, int r, int v){
        if(lazy[v]==0) return;

        update_node(v*2+1, lazy[v]);
        update_node(v*2+2, lazy[v]);
        lazy[v]=0;
    }

    int update(int l, int r, int v, int ql, int qr, int add){
        if(qr<=l || r<=ql) return tree[v];
        if(ql<=l && r<=qr){
            return update_node(v, add);
        }
        propagate(l, r, v);
        int m=l+(r-l)/2;
        return tree[v] = max(update(l, m, v*2+1, ql, qr, add), update(m, r, v*2+2, ql, qr, add));
    }

    int query(int l, int r, int v, int ql, int qr){
        if(qr<=l || r<=ql) return 0;
        if(ql<=l && r<=qr){
            return tree[v];
        }
        int m=l+(r-l)/2;
        return max(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
    }
};

struct segtree2{
    vector<int> tree;

    void init(int n){
        tree.assign(n*4, 0);
    }

    int update(int l, int r, int v, int x, int val){
        if(x<l || r<=x) return tree[v];
        if(l+1==r){
            return tree[v]=val;
        }
        int m=l+(r-l)/2;
        return tree[v] = max(update(l, m, v*2+1, x, val), update(m, r, v*2+2, x, val));
    }

    int query(){
        return tree[0];
    }
};

struct tree{
    int n;
    vector<pair<int,int> > edge;
    vector<vector<pair<int,int> > >adi;

    segtree2 segans;

    vector<int> level;
    vector<int> pc; //parent centroid

    vector<int> subtreesize;

    vector<int> curind;
    vector<set<pair<int, int> > >children;
    vector<set<pair<int, int> > >paths;

    vector<vector<int> > preind;
    vector<vector<int> > ssize;
    vector<vector<int> > paredge;
    vector<segtree> seg;

    tree(int ninput){
        n = ninput;
        edge.assign(n-1, {-1, -1});
        adi.assign(n, {});

        segans.init(n);

        level.assign(n, INF);
        pc.assign(n, -1);

        subtreesize.assign(n, 0);

        curind.assign(L, 0);
        children.assign(n, {});
        paths.assign(n, {});

        preind.assign(L, vector<int>(n, 0));
        ssize.assign(L, vector<int> (n, 0));
        paredge.assign(L, vector<int> (n, 0));
        seg.assign(L, segtree(n));
    }

    //centroids
    int dfs(int v, int p, int lev){ //precomputes the subtreesizes
 
        subtreesize[v] = 1;
        for(auto [u, d]: adi[v]){
            if(u==p || level[u]<lev) continue;

            subtreesize[v] += dfs(u, v, lev);
        }

        return subtreesize[v];
    }

    int centroiddfs(int v, int lev, int size){ //finds a centroid in a connected graph

        for(auto [u, d]: adi[v]){
            if(level[u] < lev) continue;

            if(subtreesize[u] > size/2){

                subtreesize[v] = size - subtreesize[u];
                return centroiddfs(u, lev, size);
            }
        }

        return v;
    }

    void find_centroids(int v, int lev, int centroidp){ //finds all centroids recursively
        int size = dfs(v, -1, lev);

        int centroid = centroiddfs(v, lev, size);
        level[centroid] = lev;
        pc[centroid]= centroidp;

        //compute all values for this component
        int momind = 0;
        distancedfs(centroid, -1, 0, lev, momind);
        
        for(auto [u, d]: adi[centroid]){
            if(level[u] < lev) continue;

            children[centroid].insert({preind[lev][u], u});
            int p = seg[lev].query(0, n, 0, preind[lev][u], preind[lev][u] + ssize[lev][u]);
            paths[centroid].insert({p, u});
        }
        paths[centroid].insert({0, -1});
        paths[centroid].insert({0, -2});

        int diameter = (*prev(paths[centroid].end())).first;
        diameter += (*prev(prev(paths[centroid].end()))).first;
    
        segans.update(0, n, 0, centroid, diameter);

        //find next centroids
        for(auto [u, d]: adi[centroid]){
            if(level[u] < lev) continue;

            find_centroids(u, lev+1, centroid);
        }
    }

    int distancedfs(int v, int p, int dist, int lev, int& momind){

        preind[lev][v] = momind;
        momind++;

        seg[lev].update(0, n, 0, preind[lev][v], preind[lev][v]+1, dist);

        int s=1;
        for(auto [u, d]: adi[v]){
            if(u==p || level[u] < lev) continue;

            paredge[lev][u] = d;
            s += distancedfs(u, v, dist+d, lev, momind);
        }

        ssize[lev][v] = s;
        return s;
    }


    int update_edge(int a, int b, int val){

        int c; 
        if(level[a] > level[b]){

            c=a;    
        }
        else{

            c=b;
        }
        c = pc[c];

        while(c!=-1){
            int lev = level[c];

            if(preind[lev][b]<preind[lev][a]){ 

                swap(a, b);
            } //=> a is an ancestor of b


            // update c
            int x = (*prev(children[c].upper_bound({preind[lev][b], b}))).second;
            int oldp = seg[lev].query(0, n, 0, preind[lev][x], preind[lev][x] + ssize[lev][x]);
            paths[c].erase({oldp, x});

            int add = val- paredge[lev][b];
            paredge[lev][b] = val;
            seg[lev].update(0, n, 0, preind[lev][b], preind[lev][b]+ssize[lev][b], add);

            int newp = seg[lev].query(0, n, 0, preind[lev][x], preind[lev][x] + ssize[lev][x]);
            paths[c].insert({newp, x});


            int diameterc = (*prev(paths[c].end())).first;
            diameterc += (*prev(prev(paths[c].end()))).first;
            
            segans.update(0, n, 0, c, diameterc);

            c = pc[c];
        }

        return segans.query();
    }
};

/*int solve(int n, vector<int>& v, vector<int>& u, vector<int>& w){
    tree g(n);

    for(int i=0; i<n-1; i++){
        int a=v[i];
        int b=u[i];
        int c=w[i];

        g.edge[i]={a, b};
        g.adi[a].push_back({b, c});
        g.adi[b].push_back({a, c});
    }

    g.find_centroids(0, 0, -1);

    int ans=g.segans.query();
    return ans;
}*/

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q, maxw;
    cin >> n >> q >> maxw;

    /*vector<int> v(n-1);
    vector<int> u(n-1);
    vector<int> w(n-1);
    for(int i=0; i<n-1; i++){
        cin >> v[i] >> u[i] >> w[i];
        v[i]--;
        u[i]--;
    }

    int last=0;
    for(int i=0; i<q; i++){

        int di, wi;
        cin >> di >> wi;

        int d = (di + last) % (n-1);
        int weight = (wi + last) % maxw;

        w[d] = weight;

        int ans= solve(n, v, u, w);
        cout << ans << "\n";
        last = ans;
    }*/

    tree g(n);

    for(int i=0; i<n-1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;

        g.edge[i]={a, b};
        g.adi[a].push_back({b, c});
        g.adi[b].push_back({a, c});
    }

    g.find_centroids(0, 0, -1);

    int last=0;
    for(int i=0; i<q; i++){

        int di, wi;
        cin >> di >> wi;

        int d = (di + last) % (n-1);
        int w = (wi + last) % maxw;

        auto [a, b] = g.edge[d];


        int ans=g.update_edge(a, b, w);
        cout << ans << "\n";
        
        last = ans;
    }
}

Subtask #1
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	340 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	340 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	10 ms	468 KB	Output is correct
5	Correct	46 ms	712 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	1620 KB	Output is correct
8	Correct	1 ms	1620 KB	Output is correct
9	Correct	3 ms	1620 KB	Output is correct
10	Correct	18 ms	1664 KB	Output is correct
11	Correct	77 ms	2084 KB	Output is correct
12	Correct	11 ms	13716 KB	Output is correct
13	Correct	10 ms	13716 KB	Output is correct
14	Correct	13 ms	13664 KB	Output is correct
15	Correct	33 ms	13896 KB	Output is correct
16	Correct	136 ms	14256 KB	Output is correct
17	Correct	234 ms	264356 KB	Output is correct
18	Correct	231 ms	264256 KB	Output is correct
19	Correct	248 ms	264344 KB	Output is correct
20	Correct	281 ms	264480 KB	Output is correct
21	Correct	592 ms	264936 KB	Output is correct