oj.uz

Submission #834737

# Submission time Handle Problem Language Result Execution time Memory
834737 2023-08-22T18:03:57 Z jasmin Dynamic Diameter (CEOI19_diameter) C++17
24 / 100
 3921 ms 257716 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int INF=1e18;
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
        //cout << "centroid dfs " << v << " " << lev << " " << size << " " << "\n";

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

        int diameter = 0;
        if(paths[centroid].size()>0){
            diameter += (*prev(paths[centroid].end())).first;
        }
        if(paths[centroid].size()>1){
            diameter += (*prev(prev(paths[centroid].end()))).first;
        }
        segans.update(0, n, 0, centroid, diameter);

        //cout << "centroid: " << centroid << " " << lev << " " << diameter << "\n";

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

        for(; lev>=0; lev--){
            //cout << "update centroid " << c << " " << lev << "\n";

            if(paths[c].size()==0){ //single node doesn't need update
                c = pc[c];
                continue;
            }

            if(preind[lev][b]<preind[lev][a]){ //=> a is an ancestor of b
                swap(a, b);
            }

            /*cout << preind[lev][b] << "\n";
            for(auto [i, j]: children[c]){
                cout << "(" << i << ", " << j << ") ";
            }
            cout << "\n";*/

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

            //cout << x << " " << newp << "\n";

            int diameterc = (*prev(paths[c].end())).first;
            if(paths.size()>=2){

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

            //cout << "=> " << diameterc << "\n";

            c = pc[c];
        }

        return segans.query();
    }
};

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

    int n, q, maxw;
    cin >> n >> q >> maxw;
    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++){
        //cout << "update " << i << "\n" << flush;

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

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

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

        //cout << d << " " << w << ": " << a << " " << b << "\n" << flush;

        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 0 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 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
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 2 ms 340 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 45 ms 744 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2772 KB Output is correct
2 Correct 27 ms 2892 KB Output is correct
3 Correct 129 ms 3076 KB Output is correct
4 Correct 245 ms 3360 KB Output is correct
5 Incorrect 44 ms 25720 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 2324 ms 253884 KB Output is correct
2 Correct 2488 ms 253836 KB Output is correct
3 Correct 2508 ms 253908 KB Output is correct
4 Correct 2394 ms 253764 KB Output is correct
5 Correct 2351 ms 253780 KB Output is correct
6 Correct 2114 ms 253444 KB Output is correct
7 Correct 3241 ms 255320 KB Output is correct
8 Correct 3368 ms 255300 KB Output is correct
9 Correct 3634 ms 255468 KB Output is correct
10 Correct 3576 ms 255372 KB Output is correct
11 Correct 3460 ms 255256 KB Output is correct
12 Correct 3278 ms 254848 KB Output is correct
13 Correct 3921 ms 257564 KB Output is correct
14 Correct 3743 ms 257568 KB Output is correct
15 Correct 3621 ms 257504 KB Output is correct
16 Correct 3816 ms 257548 KB Output is correct
17 Correct 3677 ms 257192 KB Output is correct
18 Correct 3348 ms 255988 KB Output is correct
19 Correct 3689 ms 257716 KB Output is correct
20 Correct 3664 ms 257552 KB Output is correct
21 Correct 3675 ms 257688 KB Output is correct
22 Correct 3687 ms 257472 KB Output is correct
23 Correct 3584 ms 257284 KB Output is correct
24 Correct 3198 ms 255892 KB Output is correct

Subtask #6
0 / 27.0

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