oj.uz

Submission #1075916

# Submission time Handle Problem Language Result Execution time Memory
1075916 2024-08-26T09:45:30 Z _8_8_ Petrol stations (CEOI24_stations) C++17
100 / 100
 1191 ms 275256 KB 
#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 7e4 + 12, MOD = 998244353;

mt19937 rng(123231);
struct node{
    node *l = 0,*r = 0;
    ll prior = 0,rem = 0,col = 0,sum =0 ,add = 0;
    node(ll val,ll c){
        prior = rng();
        rem = val;
        col = sum = c;
    }
    node(){
        prior = 0;
        rem = 0;
        col = 0;
        sum = 0;
        add = 0;
    }
};
using pnode = node *;
int sum(pnode v) {
    return v ? v->sum : 0;
}
void upd(pnode x) {
    x->sum = sum(x->l) + sum(x->r) + x->col;
}
void inc(pnode v,int val) {
    if(v) {
        v->rem += val;
        v->add += val;
    }
}
void push(pnode v) {
    inc(v->l,v->add);
    inc(v->r,v->add);
    v->add = 0;
}
pnode merge(pnode a,pnode b) {
    if(!a) return b;
    if(!b) return a;
    if(a->prior < b->prior) {
        push(b);
        b->l = merge(a,b->l);
        upd(b);
        return b;
    } else {
        push(a);
        a->r = merge(a->r,b);
        upd(a);
        return a;
    }
}
pair<pnode,pnode> split(pnode v,int key) {
    if(!v) return {0,0};
    push(v);
    if(v->rem < key) {
        auto [l,r] = split(v->r,key);
        v->r = l;
        upd(v);
        return {v,r};
    } else {
        auto [l,r] = split(v->l,key);
        v->l = r;
        upd(v);
        return {l,v};
    }   
}
vector<pair<int,int>> g[N];
vector<int> G[N];
int n, k, s[N];
bool blocked[N];
void prec(int v,int pr = -1) {
    s[v] = 1;
    for(int to:G[v]) {
        if(to == pr || blocked[to]) continue;
        prec(to,v);
        s[v] += s[to];
    }
}
int find(int v,int pr,int total) {
    for(int to:G[v]) {
        if(to == pr || blocked[to]) continue;
        if(s[to] > total / 2) {
            return find(to,v,total);
        }
    }
    return v;
}
ll ans[N];
pnode root;
int rem[N],cc[N];
void ins(int val) {
    auto [l,r] = split(root,val);
    pnode nv = new node(val,1);
    root = merge(merge(l,nv),r);
}
void cl(int v,int pr) {
    cc[v] = 0;
    for(int to:G[v]) if(!blocked[to] && to != pr) {
        cl(to,v);
    }
}
pair<pnode,pnode> split1(pnode v) {
    if(!v) return {0,0};
    push(v);
    if(v->r) {
        auto [l,r] = split1(v->r);
        v->r = l;
        upd(v);
        return {v,r};
    } else {
        auto t = v->l;
        v->l = nullptr;
        return {t,v};
    }
}
void go(int v,int pr,ll W) {
    auto [l,r] = split(root,W);
    int _s = sum(l);
    inc(r,-W);
    root = merge(r,new node(k - W,_s));
    ans[pr] += _s * 1ll * s[v];
    for(auto [to,w]:g[v]) {
        if(to == pr || blocked[to]) continue;
        go(to,v,w);
    }
    auto [t,f] = split1(root);
    inc(t,W);
    root = merge(l,t);
}
int total,pt;
bool REV = false;
void add(int v,int pr, vector<pair<int,ll>> &st) {
    ll c = k;
    rem[v] = -1;
    int vert = -1;
    // for(int i = (int)st.size() - 1;i >= 0;i--) {
    //     c -= st[i].second;
    //     if(c < 0) {
    //         rem[v] = rem[st[i + 1].first];
    //         vert = st[i +1].first;
    //         break;
    //     }
    // }
    int l = -1,r = (int)st.size() - 1;
    while(r - l > 1) {
        int mid = (l +r) >> 1;
        ll val = k - (st.back().second - (mid ? st[mid - 1].second : 0));
        if(val >= 0) {
            r = mid;
        } else {
            l = mid;
        }
    }
    if(r == 0) {
        rem[v] = k - st.back().second;
    } else {
        vert = st[r].first;
        rem[v] = rem[vert];
    }
    // cout << v << ' ' << rem[v] << ' ' << vert << ' ' << "| " << r << '\n';
    assert(rem[v] >= 0);
    ins(rem[v]);  
    cc[v]++;
    for(auto [to,w]:g[v]) {
        if(to == pr || blocked[to]) continue;
        st.push_back({v,w + st.back().second});
        add(to,v,st);
        st.pop_back();
    }
    if(vert != -1) {
        cc[vert] += cc[v];
        if(!REV) ans[vert] += cc[v] * (total - s[pt]);
    }
}
void decompose(int v) {
    prec(v);
    v = find(v,-1,s[v]);
    blocked[v] = 1;
    prec(v);
    total = s[v];
    root = new node();
    rem[v] = k;
    ins(k);
    REV = false;
    cc[v] = 0;
    for(auto [to,w]:g[v]) if(!blocked[to]) {
        go(to,v,w);
        vector<pair<int,ll>> bf = {make_pair(v,w)};
        cl(to,v);
        pt =to;
        add(to,v,bf);
    }
    root = new node();
    reverse(g[v].begin(),g[v].end());
    REV = 1;
    for(auto [to,w]:g[v]) if(!blocked[to]) {
        go(to,v,w);
        vector<pair<int,ll>> bf = {make_pair(v,w)};
        cl(to,v);
        add(to,v,bf);
    }
    for(int to:G[v]) if(!blocked[to]) {
          decompose(to);
    }
}
void test() {
    cin >> n >> k;
    for(int i = 1; i <= n - 1; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        a++;
        b++;
        g[a].push_back({b,c});G[a].push_back(b);
        g[b].push_back({a,c});G[b].push_back(a);
    }
    decompose(1);
    for(int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

Compilation message

Main.cpp: In function 'void add(int, int, std::vector<std::pair<int, long long int> >&)':
Main.cpp:139:8: warning: unused variable 'c' [-Wunused-variable]
  139 |     ll c = k;
      |        ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 5 ms 6236 KB Output is correct
4 Correct 7 ms 6748 KB Output is correct
5 Correct 4 ms 5980 KB Output is correct
6 Correct 9 ms 7172 KB Output is correct
7 Correct 7 ms 7260 KB Output is correct
8 Correct 1 ms 4952 KB Output is correct
9 Correct 5 ms 6232 KB Output is correct
10 Correct 4 ms 6236 KB Output is correct
11 Correct 5 ms 6352 KB Output is correct
12 Correct 4 ms 6232 KB Output is correct
13 Correct 5 ms 6236 KB Output is correct
14 Correct 2 ms 5468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 798 ms 274860 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 798 ms 274860 KB Output is correct
5 Correct 1106 ms 274760 KB Output is correct
6 Correct 1191 ms 274580 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 906 ms 233656 KB Output is correct
4 Correct 1014 ms 274988 KB Output is correct
5 Correct 963 ms 275256 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 675 ms 211452 KB Output is correct
8 Correct 743 ms 217940 KB Output is correct
9 Correct 681 ms 212564 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 906 ms 233656 KB Output is correct
4 Correct 1014 ms 274988 KB Output is correct
5 Correct 963 ms 275256 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 675 ms 211452 KB Output is correct
8 Correct 743 ms 217940 KB Output is correct
9 Correct 681 ms 212564 KB Output is correct
10 Correct 396 ms 121652 KB Output is correct
11 Correct 503 ms 156660 KB Output is correct
12 Correct 524 ms 165656 KB Output is correct
13 Correct 526 ms 164944 KB Output is correct
14 Correct 517 ms 159828 KB Output is correct
15 Correct 539 ms 162820 KB Output is correct
16 Correct 130 ms 41924 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 5 ms 6236 KB Output is correct
4 Correct 7 ms 6748 KB Output is correct
5 Correct 4 ms 5980 KB Output is correct
6 Correct 9 ms 7172 KB Output is correct
7 Correct 7 ms 7260 KB Output is correct
8 Correct 1 ms 4952 KB Output is correct
9 Correct 5 ms 6232 KB Output is correct
10 Correct 4 ms 6236 KB Output is correct
11 Correct 5 ms 6352 KB Output is correct
12 Correct 4 ms 6232 KB Output is correct
13 Correct 5 ms 6236 KB Output is correct
14 Correct 2 ms 5468 KB Output is correct
15 Correct 1 ms 4956 KB Output is correct
16 Correct 798 ms 274860 KB Output is correct
17 Correct 1106 ms 274760 KB Output is correct
18 Correct 1191 ms 274580 KB Output is correct
19 Correct 906 ms 233656 KB Output is correct
20 Correct 1014 ms 274988 KB Output is correct
21 Correct 963 ms 275256 KB Output is correct
22 Correct 1 ms 4952 KB Output is correct
23 Correct 675 ms 211452 KB Output is correct
24 Correct 743 ms 217940 KB Output is correct
25 Correct 681 ms 212564 KB Output is correct
26 Correct 396 ms 121652 KB Output is correct
27 Correct 503 ms 156660 KB Output is correct
28 Correct 524 ms 165656 KB Output is correct
29 Correct 526 ms 164944 KB Output is correct
30 Correct 517 ms 159828 KB Output is correct
31 Correct 539 ms 162820 KB Output is correct
32 Correct 130 ms 41924 KB Output is correct
33 Correct 990 ms 207440 KB Output is correct
34 Correct 437 ms 122192 KB Output is correct
35 Correct 540 ms 165204 KB Output is correct
36 Correct 543 ms 163920 KB Output is correct
37 Correct 715 ms 162548 KB Output is correct
38 Correct 788 ms 166208 KB Output is correct
39 Correct 723 ms 166892 KB Output is correct
40 Correct 216 ms 42696 KB Output is correct