oj.uz

Submission #837834

# Submission time Handle Problem Language Result Execution time Memory
837834 2023-08-25T18:29:51 Z jasmin Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 4149 ms 270768 KB 
#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 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(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];
        }
        propagate(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
        distancedfs(centroid, -1, 0, lev);
        
        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){

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

        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);
        }

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


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

        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});


            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);

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

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

    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];

        //cout << "update " << d << " " << a+1 << " " << b+1 << " " << w << "\n";

        int add = w - c[d];
        c[d] = w;
        
        int ans=g.update_edge(a, b, add);
        cout << ans << "\n";
        
        last = ans;
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 10 ms 412 KB Output is correct
5 Correct 49 ms 724 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 2 ms 1532 KB Output is correct
8 Correct 2 ms 1616 KB Output is correct
9 Correct 3 ms 1652 KB Output is correct
10 Correct 17 ms 1664 KB Output is correct
11 Correct 79 ms 2060 KB Output is correct
12 Correct 10 ms 13716 KB Output is correct
13 Correct 14 ms 13716 KB Output is correct
14 Correct 16 ms 13716 KB Output is correct
15 Correct 33 ms 13788 KB Output is correct
16 Correct 155 ms 14256 KB Output is correct
17 Correct 317 ms 265132 KB Output is correct
18 Correct 255 ms 265100 KB Output is correct
19 Correct 249 ms 265140 KB Output is correct
20 Correct 291 ms 265244 KB Output is correct
21 Correct 584 ms 265660 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2900 KB Output is correct
2 Correct 31 ms 2988 KB Output is correct
3 Correct 153 ms 3156 KB Output is correct
4 Correct 292 ms 3396 KB Output is correct
5 Incorrect 48 ms 26972 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2700 ms 270076 KB Output is correct
2 Correct 2889 ms 267172 KB Output is correct
3 Correct 3038 ms 267168 KB Output is correct
4 Correct 2884 ms 267096 KB Output is correct
5 Correct 2884 ms 266988 KB Output is correct
6 Correct 2617 ms 266860 KB Output is correct
7 Correct 3757 ms 268624 KB Output is correct
8 Correct 3579 ms 268540 KB Output is correct
9 Correct 3702 ms 268564 KB Output is correct
10 Correct 3656 ms 268564 KB Output is correct
11 Correct 3649 ms 268492 KB Output is correct
12 Correct 3463 ms 268052 KB Output is correct
13 Correct 4072 ms 270768 KB Output is correct
14 Correct 4019 ms 270736 KB Output is correct
15 Correct 4149 ms 270756 KB Output is correct
16 Correct 4070 ms 270720 KB Output is correct
17 Correct 3945 ms 270280 KB Output is correct
18 Correct 3674 ms 269164 KB Output is correct
19 Correct 3957 ms 270736 KB Output is correct
20 Correct 4099 ms 270740 KB Output is correct
21 Correct 3959 ms 270696 KB Output is correct
22 Correct 3981 ms 270620 KB Output is correct
23 Correct 3833 ms 270276 KB Output is correct
24 Correct 3571 ms 269080 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -