oj.uz

Submission #1100698

# Submission time Handle Problem Language Result Execution time Memory
1100698 2024-10-14T13:10:41 Z not_amir Petrol stations (CEOI24_stations) C++14
18 / 100
 812 ms 233796 KB 
#include <bits/stdc++.h>
using namespace std;

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

ll INF;

struct Vertex {
    Vertex* l, * r;
    int 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);
    }
};

int 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> jumpw, parw;
vector<int> ans, res, 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 = ll(n) * ll(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:59:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'int get_centroid(int, int, int)':
Main.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'void dfs1(Vertex*, int, int, int, int, int)':
Main.cpp:92:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void dfs2(Vertex*, int, int, ll, int)':
Main.cpp:120:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void centroid_decomp(int)':
Main.cpp:147:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  147 |     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 4856 KB Output is correct
4 Correct 7 ms 3408 KB Output is correct
5 Correct 7 ms 4176 KB Output is correct
6 Correct 12 ms 6736 KB Output is correct
7 Correct 7 ms 3152 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 8 ms 4700 KB Output is correct
10 Correct 8 ms 4688 KB Output is correct
11 Correct 9 ms 4688 KB Output is correct
12 Correct 8 ms 4688 KB Output is correct
13 Correct 8 ms 4688 KB Output is correct
14 Correct 4 ms 2896 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 702 ms 186184 KB Output isn't correct
3 Halted 0 ms 0 KB -

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 1 ms 336 KB Output is correct
4 Incorrect 702 ms 186184 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.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 663 ms 187868 KB Output is correct
4 Incorrect 812 ms 233796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0.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 663 ms 187868 KB Output is correct
4 Incorrect 812 ms 233796 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 4856 KB Output is correct
4 Correct 7 ms 3408 KB Output is correct
5 Correct 7 ms 4176 KB Output is correct
6 Correct 12 ms 6736 KB Output is correct
7 Correct 7 ms 3152 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 8 ms 4700 KB Output is correct
10 Correct 8 ms 4688 KB Output is correct
11 Correct 9 ms 4688 KB Output is correct
12 Correct 8 ms 4688 KB Output is correct
13 Correct 8 ms 4688 KB Output is correct
14 Correct 4 ms 2896 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Incorrect 702 ms 186184 KB Output isn't correct
17 Halted 0 ms 0 KB -