oj.uz

Submission #834751

# Submission time Handle Problem Language Result Execution time Memory
834751 2023-08-22T18:13:20 Z jasmin Dynamic Diameter (CEOI19_diameter) C++17
24 / 100
 4309 ms 257520 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 1 ms 384 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 384 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 11 ms 720 KB Output is correct
5 Correct 46 ms 912 KB Output is correct
6 Incorrect 1 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 6 ms 2772 KB Output is correct
2 Correct 27 ms 2980 KB Output is correct
3 Correct 126 ms 3332 KB Output is correct
4 Correct 249 ms 3424 KB Output is correct
5 Incorrect 41 ms 25812 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 2342 ms 254252 KB Output is correct
2 Correct 2497 ms 253988 KB Output is correct
3 Correct 2520 ms 253836 KB Output is correct
4 Correct 2484 ms 253776 KB Output is correct
5 Correct 2390 ms 253700 KB Output is correct
6 Correct 2128 ms 253484 KB Output is correct
7 Correct 3188 ms 255284 KB Output is correct
8 Correct 3290 ms 255232 KB Output is correct
9 Correct 3225 ms 255296 KB Output is correct
10 Correct 3253 ms 255232 KB Output is correct
11 Correct 3152 ms 255136 KB Output is correct
12 Correct 2898 ms 254784 KB Output is correct
13 Correct 3735 ms 257404 KB Output is correct
14 Correct 3526 ms 257372 KB Output is correct
15 Correct 3552 ms 257460 KB Output is correct
16 Correct 3665 ms 257340 KB Output is correct
17 Correct 3576 ms 257124 KB Output is correct
18 Correct 3161 ms 255864 KB Output is correct
19 Correct 3615 ms 257380 KB Output is correct
20 Correct 3620 ms 257460 KB Output is correct
21 Correct 4309 ms 257364 KB Output is correct
22 Correct 3924 ms 257520 KB Output is correct
23 Correct 3369 ms 257044 KB Output is correct
24 Correct 2991 ms 255732 KB Output is correct

Subtask #6
0 / 27.0

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