oj.uz

Submission #1100652

# Submission time Handle Problem Language Result Execution time Memory
1100652 2024-10-14T11:42:35 Z not_amir Petrol stations (CEOI24_stations) C++14
55 / 100
 2129 ms 2097152 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")

typedef pair<int, int> pii;
typedef long long ll;

ll INF;

struct Vertex {
    Vertex* l, * r;
    ll sum;

    Vertex(ll val) : l(nullptr), r(nullptr), sum(val) {}
    Vertex(Vertex* l, Vertex* r) : l(l), r(r), sum(0) {
        if (l) sum += l->sum;
        if (r) sum += r->sum;
    }

    void extend(){
        if(!l)
            l = new Vertex(0);
        if(!r)
            r = new Vertex(0);
    }
};

ll get_sum(Vertex* v, ll tl, ll tr, ll l, ll r) {
    if (l + 1 > r)
        return 0;
    if (l == tl && tr == r)
        return v->sum;
    if(v->l == nullptr)
        return 0;
    ll tm = (tl + tr) / 2;
    return get_sum(v->l, tl, tm, l, min(r, tm))
        + get_sum(v->r, tm, tr, max(l, tm), r);
}

void update(Vertex* v, ll tl, ll tr, ll pos, int new_val) {
    if (tl + 1 == tr){
        v->sum += new_val;
        return;
    }
    v->extend();
    ll tm = (tl + tr) / 2;
    if (pos < tm)
        update(v->l, tl, tm, pos, new_val);
    else
        update(v->r, tm, tr, pos, new_val);
    v->sum = v->l->sum + v->r->sum;
}

vector<vector<pii>> G;
vector<bool> is_removed;
vector<int> subsize;

int get_subtree_size(int v, int p = -1) {
    subsize[v] = 1;
    for (auto [u, w] : G[v]) {
        if (u == p || is_removed[u]) { continue; }
        subsize[v] += get_subtree_size(u, v);
    }
    return subsize[v];
}

int get_centroid(int v, int S, int p = -1) {
    for (auto [u, w] : G[v]) {
        if (u == p || is_removed[u]) { continue; }
        if (subsize[u] * 2 > S) {
            return get_centroid(u, S, v);
        }
    }
    return v;
}

int k;

vector<ll> ans, res, jumpw, parw;
vector<int> depth, jump, par;

vector<Vertex*> st;

void dfs1(Vertex* stt, int v, int p, int d, int child, int S) {
    depth[v] = d;
    res[v] = 0;
    if(p != -1) {
        if(depth[jump[p]] - depth[p] == depth[jump[jump[p]]] - depth[jump[p]])
            jump[v] = jump[jump[p]], jumpw[v] = jumpw[jump[p]] + jumpw[p] + parw[v];
        else
            jump[v] = p, jumpw[v] = parw[v];
    }
    for(auto [u, w] : G[v]) {
        if(u == p || is_removed[u])
            continue;
        par[u] = v, parw[u] = w;
        if(p == -1)
            st[u] = new Vertex(0);
        dfs1(stt, u, v, d + 1, p==-1?u:child, S);
    }
    if(p != -1) {
        int a = v;
        ll s = 0;
        ans[v] += res[v] * (S - subsize[child]);
        while(jump[a] != a && s + parw[a] <= k) {
            if(jumpw[a] + s <= k)
                s += jumpw[a], a = jump[a];
            else
                s += parw[a], a = par[a];
        }
        if(jump[a] == a) {
            update(stt, 0, INF, k - s, res[v] + 1);
            update(st[child], 0, INF, k - s, res[v] + 1);
        }
        else
            res[a] += res[v] + 1;
    }
}

void dfs2(Vertex* stt, int v, int p, ll s, int child) {
    for(auto [u, w] : G[v]) {
        if(u == p || is_removed[u])
            continue;
        if(p == -1)
            child = u;
        int refuel = get_sum(stt, 0, INF, s, s + w);
        refuel -= get_sum(st[child], 0, INF, s, s + w);
        ans[v] += refuel * subsize[u];
        update(stt, 0, INF, s + k, refuel);
        dfs2(stt, u, v, s + w, child);
        update(stt, 0, INF, s + k, -refuel);
    }
}

void centroid_decomp(int v = 0) {
    int centroid = get_centroid(v, get_subtree_size(v));

    Vertex* stt = new Vertex(0);

    jump[centroid] = centroid;
    jumpw[centroid] = 0;
    dfs1(stt, centroid, -1, 0, 0, get_subtree_size(centroid));
    update(stt, 0, INF, k, 1);
    dfs2(stt, centroid, -1, 0, 0);

    is_removed[centroid] = true;

    for (auto [u, w] : G[centroid]) {
        if (is_removed[u]) { continue; }
        centroid_decomp(u);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n >> k;
    INF = n * k;
    G.resize(n);
    is_removed.resize(n);
    subsize.resize(n);
    par.resize(n);
    parw.resize(n);
    jump.resize(n);
    jumpw.resize(n);
    ans.resize(n);
    res.resize(n);
    depth.resize(n);
    st.resize(n);
    for(int i = 0; i < n - 1; i++) {
        int u, v, l;
        cin >> u >> v >> l;
        G[u].push_back({v, l});
        G[v].push_back({u, l});
    }
    centroid_decomp();
    for(int i = 0; i < n; i++)
        cout << ans[i] << '\n';
}

Compilation message

Main.cpp: In function 'int get_subtree_size(int, int)':
Main.cpp:61:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'int get_centroid(int, int, int)':
Main.cpp:69:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'void dfs1(Vertex*, int, int, int, int, int)':
Main.cpp:94:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void dfs2(Vertex*, int, int, ll, int)':
Main.cpp:122:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void centroid_decomp(int)':
Main.cpp:149:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  149 |     for (auto [u, w] : G[centroid]) {
      |               ^

Subtask #0
0.0 / 0.0

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 8 ms 4604 KB Output is correct
4 Correct 10 ms 3408 KB Output is correct
5 Correct 7 ms 4176 KB Output is correct
6 Correct 13 ms 6992 KB Output is correct
7 Correct 7 ms 3064 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 8 ms 4856 KB Output is correct
10 Correct 8 ms 4688 KB Output is correct
11 Correct 8 ms 4688 KB Output is correct
12 Correct 13 ms 4676 KB Output is correct
13 Correct 8 ms 4612 KB Output is correct
14 Correct 4 ms 2896 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 716 ms 189020 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 716 ms 189020 KB Output is correct
5 Runtime error 2129 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 606 ms 188492 KB Output is correct
4 Correct 785 ms 236724 KB Output is correct
5 Correct 716 ms 186348 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 696 ms 212040 KB Output is correct
8 Correct 644 ms 212040 KB Output is correct
9 Correct 661 ms 212284 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 606 ms 188492 KB Output is correct
4 Correct 785 ms 236724 KB Output is correct
5 Correct 716 ms 186348 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 696 ms 212040 KB Output is correct
8 Correct 644 ms 212040 KB Output is correct
9 Correct 661 ms 212284 KB Output is correct
10 Correct 450 ms 190280 KB Output is correct
11 Correct 472 ms 189000 KB Output is correct
12 Correct 465 ms 179784 KB Output is correct
13 Correct 581 ms 200776 KB Output is correct
14 Correct 503 ms 200776 KB Output is correct
15 Correct 526 ms 200776 KB Output is correct
16 Correct 242 ms 165056 KB Output is correct

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 8 ms 4604 KB Output is correct
4 Correct 10 ms 3408 KB Output is correct
5 Correct 7 ms 4176 KB Output is correct
6 Correct 13 ms 6992 KB Output is correct
7 Correct 7 ms 3064 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 8 ms 4856 KB Output is correct
10 Correct 8 ms 4688 KB Output is correct
11 Correct 8 ms 4688 KB Output is correct
12 Correct 13 ms 4676 KB Output is correct
13 Correct 8 ms 4612 KB Output is correct
14 Correct 4 ms 2896 KB Output is correct
15 Correct 0 ms 336 KB Output is correct
16 Correct 716 ms 189020 KB Output is correct
17 Runtime error 2129 ms 2097152 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -