oj.uz

답안 #837789

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
837789 2023-08-25T17:19:42 Z jasmin Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 3972 ms 274104 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--;

        for(; lev>=0; lev--){

            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];
        }
        assert(c==-1);

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

Subtask #2
0 / 13.0

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

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 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 9 ms 464 KB Output is correct
5 Correct 46 ms 732 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 16 ms 1620 KB Output is correct
11 Correct 72 ms 2844 KB Output is correct
12 Correct 11 ms 13752 KB Output is correct
13 Correct 11 ms 13708 KB Output is correct
14 Correct 13 ms 13716 KB Output is correct
15 Correct 31 ms 14016 KB Output is correct
16 Correct 111 ms 15208 KB Output is correct
17 Correct 245 ms 265528 KB Output is correct
18 Correct 235 ms 265460 KB Output is correct
19 Correct 239 ms 265580 KB Output is correct
20 Correct 280 ms 265828 KB Output is correct
21 Correct 517 ms 267096 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2900 KB Output is correct
2 Correct 27 ms 3016 KB Output is correct
3 Correct 127 ms 3656 KB Output is correct
4 Correct 247 ms 4320 KB Output is correct
5 Incorrect 45 ms 27056 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2387 ms 268184 KB Output is correct
2 Correct 2465 ms 270492 KB Output is correct
3 Correct 2468 ms 270468 KB Output is correct
4 Correct 2540 ms 270424 KB Output is correct
5 Correct 2559 ms 270392 KB Output is correct
6 Correct 2255 ms 270244 KB Output is correct
7 Correct 3395 ms 271960 KB Output is correct
8 Correct 3368 ms 271940 KB Output is correct
9 Correct 3323 ms 271884 KB Output is correct
10 Correct 3245 ms 271956 KB Output is correct
11 Correct 3263 ms 271840 KB Output is correct
12 Correct 2988 ms 271520 KB Output is correct
13 Correct 3705 ms 273964 KB Output is correct
14 Correct 3972 ms 274028 KB Output is correct
15 Correct 3759 ms 274000 KB Output is correct
16 Correct 3776 ms 274080 KB Output is correct
17 Correct 3585 ms 273732 KB Output is correct
18 Correct 3221 ms 272496 KB Output is correct
19 Correct 3740 ms 274052 KB Output is correct
20 Correct 3656 ms 273988 KB Output is correct
21 Correct 3788 ms 274104 KB Output is correct
22 Correct 3919 ms 273964 KB Output is correct
23 Correct 3687 ms 273748 KB Output is correct
24 Correct 3242 ms 272552 KB Output is correct

Subtask #6
0 / 27.0

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