oj.uz

Submission #839566

# Submission time Handle Problem Language Result Execution time Memory
839566 2023-08-30T08:59:39 Z model_code Truck Driver (IOI23_deliveries) C++17
100 / 100
 3493 ms 39884 KB 
// correct/sol_na_full_log2.cpp

#include "deliveries.h"
#include <cstdlib>
#include <iostream>
#include <cassert>
#include<cmath>

using std::cerr;

#define xx first
#define yy second

using ll = long long;

class solver {
    struct segtree {
        struct node {
            ll max_subtree_w;
            ll sum_wdotd, sum_d;
            ll lazy;

            node() : max_subtree_w(0), sum_wdotd(0), sum_d(0), lazy(0) {}

            void apply_lazy() {
                max_subtree_w += lazy;
                sum_wdotd += sum_d * lazy;
            }

            node operator+(const node& other) const {
                node res = *this;
                res.max_subtree_w = std::max(res.max_subtree_w, other.max_subtree_w);
                res.sum_wdotd = res.sum_wdotd + other.sum_wdotd;
                res.sum_d = res.sum_d + other.sum_d;

                return res;
            }
        };

        std::vector<node> tree;

        segtree() {}
        segtree(int N) {
            tree.resize(4*N);
        }

        void build(int ind, int L, int R, std::vector<ll>& W, std::vector<ll>& D) {
            if(L==R) {
                tree[ind].max_subtree_w = W[L];
                tree[ind].sum_d = D[L];
                tree[ind].sum_wdotd = (ll)D[L]*W[L];
                return ;
            }else {
                build(2*ind, L, (L+R)/2, W, D);
                build(2*ind+1, (L+R)/2+1, R, W, D);

                tree[ind] = tree[2*ind]+tree[2*ind+1];
                return ;
            }
        }

        void push(int ind, int L, int R) {
            if(tree[ind].lazy!=0) {
                if(L!=R) {
                    tree[2*ind].lazy+=tree[ind].lazy;
                    tree[2*ind+1].lazy+=tree[ind].lazy;
                }

                tree[ind].apply_lazy();
                tree[ind].lazy=0;
            }
        }
        
        node query(int ind, int L, int R, int i, int j) {
            push(ind, L, R);
            if(R<i || j<L) return node();
            if(i<=L && R<=j) return tree[ind];
            return query(2*ind, L, (L+R)/2, i, j) + query(2*ind+1, (L+R)/2+1, R, i, j);
        }
        
        void update(int ind, int L, int R, int i, int j, int by) {
            push(ind, L, R);
            if(R<i || j<L) return ;
            if(i<=L && R<=j) {
                tree[ind].lazy+=by;
                push(ind, L, R);
                return ;
            }
            update(2*ind, L, (L+R)/2, i, j, by);
            update(2*ind+1, (L+R)/2+1, R, i, j, by);
            tree[ind]=tree[2*ind]+tree[2*ind+1];
        }
    };

    int N;
    std::vector<std::vector<std::pair<int,int>>> adj;
    std::vector<int> W;

    std::vector<int> sz, hld_nxt, par, par_D;
    std::vector<ll> subtree_sum;
    void dfs_sz(int x) {
        par[x]=-1;
        subtree_sum[x]=W[x];
        sz[x]=1;

        hld_nxt[x]=-1;
        
        for(auto i:adj[x]) {
            if(!sz[i.xx]) {
                dfs_sz(i.xx);
                
                par_D[i.xx]=i.yy;
                subtree_sum[x]+=subtree_sum[i.xx];
                par[i.xx]=x;
                sz[x]+=sz[i.xx];

                if(hld_nxt[x]==-1 || sz[i.xx]>sz[hld_nxt[x]]) {
                    hld_nxt[x]=i.xx;
                }
            }
        }
    }

    std::vector<int> hld, hld_id, hld_head, hld_inv;
    int hld_pos, hld_next_id;
    void dfs_hld(int x) {
        hld[x]=hld_pos++;
        hld_inv[hld_pos-1]=x;
        hld_id[x]=hld_next_id;
        if(hld_nxt[x]!=-1) {
            dfs_hld(hld_nxt[x]);
            
            for(auto i:adj[x]) {
                if(hld_nxt[x]!=i.xx && par[i.xx]==x) {
                    hld_next_id++;
                    dfs_hld(i.xx);
                }
            }
        }
        
        hld_head[hld_id[x]]=x;
    }

    segtree st;
    ll sum_w=0;
    int lg;
public:
    solver() {}

    solver(int N, std::vector<int> U_, std::vector<int> V_, std::vector<int> T_, std::vector<int> W_) : N(N), hld_pos(0), hld_next_id(0) {
        lg = log2(N)+1;
        adj.resize(N);
        for(int i=0;i<N-1;++i) {
            adj[U_[i]].push_back({V_[i], T_[i]});
            adj[V_[i]].push_back({U_[i], T_[i]});
        }
        W = std::move(W_);
        W[0]++;
        for(int w:W) sum_w+=w;

        subtree_sum.assign(N, 0);
        sz.assign(N, 0);
        hld_nxt.assign(N, 0);
        par.assign(N, -1);
        par_D.assign(N, 0);

        dfs_sz(0);
        hld.assign(N, -1);
        hld_id.assign(N, -1);
        hld_inv.assign(N, -1);
        hld_head.assign(N, -1);
        dfs_hld(0);

        st = segtree(N);
        std::vector<ll> subtree_sum_hld(N), par_D_hld(N);
        for(int i=0;i<N;++i) {
            subtree_sum_hld[hld[i]]=subtree_sum[i];
            par_D_hld[hld[i]]=par_D[i];
        }

        st.build(1,0,N-1, subtree_sum_hld, par_D_hld);
    }

    // (sum_w-subtreeSumW[i])*par_d[i] a centroidig a többi subtreeSumW[i]*par_d[i]
    // 3 * 0 + 1 * 1 - 
    ll calc_answer(ll p) {
        ll ans = st.query(1, 0, N-1, 0, N-1).sum_wdotd;
        while(1) {
            ans += -2*st.query(1, 0, N-1,  hld[hld_head[hld_id[p]]], hld[p]).sum_wdotd
                   + st.query(1, 0, N-1,  hld[hld_head[hld_id[p]]], hld[p]).sum_d * sum_w;
            p = par[hld_head[hld_id[p]]];
            if(p<0) break ;
        }

        return ans;
    }

    ll change(ll p, ll new_w) {
        if(p==0) new_w++;
        ll prv_w = W[p];
        ll change = new_w - prv_w;
        W[p] = new_w;
        sum_w+=change;

        while(1) {
            st.update(1, 0, N-1, hld[hld_head[hld_id[p]]], hld[p], change);
            p = par[hld_head[hld_id[p]]];
            if(p<0) break ;
        }
        
        int i=0;
        for(int j = lg;j>=0;j--) {
            int ii=i+(1<<j);
            if(ii<N && 2*st.query(1,0,N-1,ii,N-1).max_subtree_w>=sum_w) {
                i=ii;
            }
        }
        
        return 2*calc_answer(hld_inv[i]);
    }
};

solver s;

void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
    s = solver(N, U, V, T, W);
}

long long max_time(int X, int Y) {
    return s.change(X, Y);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7664 KB Output is correct
2 Correct 84 ms 7368 KB Output is correct
3 Correct 83 ms 7640 KB Output is correct
4 Correct 81 ms 7612 KB Output is correct
5 Correct 88 ms 7724 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 5 ms 588 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 3 ms 596 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7664 KB Output is correct
2 Correct 84 ms 7368 KB Output is correct
3 Correct 83 ms 7640 KB Output is correct
4 Correct 81 ms 7612 KB Output is correct
5 Correct 88 ms 7724 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 16 ms 612 KB Output is correct
8 Correct 199 ms 3884 KB Output is correct
9 Correct 3493 ms 32740 KB Output is correct
10 Correct 3485 ms 32736 KB Output is correct
11 Correct 3342 ms 32736 KB Output is correct
12 Correct 2149 ms 34148 KB Output is correct
13 Correct 2149 ms 34188 KB Output is correct
14 Correct 2174 ms 34148 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7664 KB Output is correct
2 Correct 84 ms 7368 KB Output is correct
3 Correct 83 ms 7640 KB Output is correct
4 Correct 81 ms 7612 KB Output is correct
5 Correct 88 ms 7724 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 7 ms 652 KB Output is correct
8 Correct 154 ms 4340 KB Output is correct
9 Correct 1976 ms 38088 KB Output is correct
10 Correct 1933 ms 38092 KB Output is correct
11 Correct 1936 ms 38168 KB Output is correct
12 Correct 1829 ms 39884 KB Output is correct
13 Correct 1934 ms 39880 KB Output is correct
14 Correct 1700 ms 38112 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7664 KB Output is correct
2 Correct 84 ms 7368 KB Output is correct
3 Correct 83 ms 7640 KB Output is correct
4 Correct 81 ms 7612 KB Output is correct
5 Correct 88 ms 7724 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 5 ms 588 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 3 ms 596 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 16 ms 612 KB Output is correct
23 Correct 199 ms 3884 KB Output is correct
24 Correct 3493 ms 32740 KB Output is correct
25 Correct 3485 ms 32736 KB Output is correct
26 Correct 3342 ms 32736 KB Output is correct
27 Correct 2149 ms 34148 KB Output is correct
28 Correct 2149 ms 34188 KB Output is correct
29 Correct 2174 ms 34148 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 7 ms 652 KB Output is correct
32 Correct 154 ms 4340 KB Output is correct
33 Correct 1976 ms 38088 KB Output is correct
34 Correct 1933 ms 38092 KB Output is correct
35 Correct 1936 ms 38168 KB Output is correct
36 Correct 1829 ms 39884 KB Output is correct
37 Correct 1934 ms 39880 KB Output is correct
38 Correct 1700 ms 38112 KB Output is correct
39 Correct 1 ms 232 KB Output is correct
40 Correct 8 ms 644 KB Output is correct
41 Correct 140 ms 4256 KB Output is correct
42 Correct 2008 ms 35768 KB Output is correct
43 Correct 2086 ms 36236 KB Output is correct
44 Correct 2062 ms 36840 KB Output is correct
45 Correct 2108 ms 37272 KB Output is correct
46 Correct 2023 ms 37700 KB Output is correct
47 Correct 1971 ms 37432 KB Output is correct
48 Correct 1844 ms 37904 KB Output is correct
49 Correct 1839 ms 38368 KB Output is correct
50 Correct 1765 ms 38768 KB Output is correct
51 Correct 1790 ms 39264 KB Output is correct
52 Correct 1924 ms 33980 KB Output is correct
53 Correct 1847 ms 33976 KB Output is correct
54 Correct 1829 ms 33980 KB Output is correct
55 Correct 1779 ms 37280 KB Output is correct
56 Correct 1834 ms 37716 KB Output is correct
57 Correct 1741 ms 37640 KB Output is correct