oj.uz

Submission #837791

# Submission time Handle Problem Language Result Execution time Memory
837791 2023-08-25T17:24:23 Z jasmin Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 4384 ms 270224 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 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
        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 val){

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

            c=a;    
            lev = level[a];
        }
        else{

            c=b;
            lev = level[b];
        }
        c = pc[c];
        lev--;

        while(c!=-1){
            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

# 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 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 9 ms 420 KB Output is correct
5 Correct 45 ms 768 KB Output is correct
6 Correct 0 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 16 ms 1748 KB Output is correct
11 Correct 72 ms 1984 KB Output is correct
12 Correct 12 ms 13696 KB Output is correct
13 Correct 13 ms 13616 KB Output is correct
14 Correct 13 ms 13716 KB Output is correct
15 Correct 36 ms 13808 KB Output is correct
16 Correct 114 ms 14196 KB Output is correct
17 Correct 232 ms 264232 KB Output is correct
18 Correct 235 ms 264388 KB Output is correct
19 Correct 231 ms 264248 KB Output is correct
20 Correct 278 ms 264408 KB Output is correct
21 Correct 545 ms 264972 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2900 KB Output is correct
2 Correct 27 ms 2984 KB Output is correct
3 Correct 126 ms 3164 KB Output is correct
4 Correct 258 ms 3432 KB Output is correct
5 Incorrect 46 ms 26960 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 2498 ms 266408 KB Output is correct
2 Correct 2613 ms 266348 KB Output is correct
3 Correct 2532 ms 266356 KB Output is correct
4 Correct 2537 ms 266368 KB Output is correct
5 Correct 2559 ms 266208 KB Output is correct
6 Correct 2322 ms 265988 KB Output is correct
7 Correct 3403 ms 267860 KB Output is correct
8 Correct 3418 ms 267816 KB Output is correct
9 Correct 3401 ms 267792 KB Output is correct
10 Correct 3509 ms 267772 KB Output is correct
11 Correct 3412 ms 267708 KB Output is correct
12 Correct 3083 ms 267204 KB Output is correct
13 Correct 3821 ms 269972 KB Output is correct
14 Correct 3710 ms 269988 KB Output is correct
15 Correct 3830 ms 270008 KB Output is correct
16 Correct 3835 ms 270012 KB Output is correct
17 Correct 3812 ms 269552 KB Output is correct
18 Correct 3391 ms 268268 KB Output is correct
19 Correct 4067 ms 269968 KB Output is correct
20 Correct 4212 ms 270208 KB Output is correct
21 Correct 4384 ms 270196 KB Output is correct
22 Correct 4273 ms 270224 KB Output is correct
23 Correct 4329 ms 269772 KB Output is correct
24 Correct 3744 ms 269400 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 -