oj.uz

Submission #1100716

# Submission time Handle Problem Language Result Execution time Memory
1100716 2024-10-14T13:50:06 Z not_amir Petrol stations (CEOI24_stations) C++17
55 / 100
 3500 ms 2082340 KB 
#include <bits/stdc++.h>
using namespace std;

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

constexpr int N = 7e4;

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<pii> G[N];
bool is_removed[N];
int subsize[N];

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;

ll ans[N], res[N];

Vertex* st[N];

void dfs1(Vertex* stt, int v, int p, int d, int child, int S, vector<pii>& path) {
    res[v] = 0;
    for(auto [u, w] : G[v]) {
        if(u == p || is_removed[u])
            continue;
        if(p == -1)
            st[u] = new Vertex(0);
        path.push_back({path.back().first + w, u});
        dfs1(stt, u, v, d + 1, p==-1?u:child, S, path);
        path.pop_back();
    }
    if(p != -1) {
        ans[v] += res[v] * (S - subsize[child]);
        auto it = lower_bound(path.begin(), path.end(), pair(path.back().first - k, -1));
        auto [s, a] = *it;
        if(s == 0) {
            update(stt, 0, INF, k - path.back().first, res[v] + 1);
            update(st[child], 0, INF, k - path.back().first, 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);

    vector<pii> path = {{0, centroid}};
    dfs1(stt, centroid, -1, 0, 0, get_subtree_size(centroid), path);
    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);
    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';
}

Subtask #0
0.0 / 0.0

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3664 KB Output is correct
2 Correct 2 ms 3664 KB Output is correct
3 Correct 9 ms 8016 KB Output is correct
4 Correct 8 ms 6844 KB Output is correct
5 Correct 8 ms 7504 KB Output is correct
6 Correct 13 ms 10320 KB Output is correct
7 Correct 7 ms 6480 KB Output is correct
8 Correct 2 ms 3664 KB Output is correct
9 Correct 9 ms 8016 KB Output is correct
10 Correct 9 ms 8004 KB Output is correct
11 Correct 9 ms 8156 KB Output is correct
12 Correct 9 ms 8016 KB Output is correct
13 Correct 10 ms 8016 KB Output is correct
14 Correct 6 ms 6224 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3832 KB Output is correct
2 Correct 691 ms 185260 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3664 KB Output is correct
2 Correct 2 ms 3664 KB Output is correct
3 Correct 2 ms 3832 KB Output is correct
4 Correct 691 ms 185260 KB Output is correct
5 Execution timed out 3705 ms 2082340 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3664 KB Output is correct
2 Correct 2 ms 3664 KB Output is correct
3 Correct 622 ms 186632 KB Output is correct
4 Correct 740 ms 232752 KB Output is correct
5 Correct 664 ms 182720 KB Output is correct
6 Correct 2 ms 3664 KB Output is correct
7 Correct 592 ms 210032 KB Output is correct
8 Correct 622 ms 210248 KB Output is correct
9 Correct 601 ms 210276 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3664 KB Output is correct
2 Correct 2 ms 3664 KB Output is correct
3 Correct 622 ms 186632 KB Output is correct
4 Correct 740 ms 232752 KB Output is correct
5 Correct 664 ms 182720 KB Output is correct
6 Correct 2 ms 3664 KB Output is correct
7 Correct 592 ms 210032 KB Output is correct
8 Correct 622 ms 210248 KB Output is correct
9 Correct 601 ms 210276 KB Output is correct
10 Correct 421 ms 188456 KB Output is correct
11 Correct 487 ms 187208 KB Output is correct
12 Correct 460 ms 177804 KB Output is correct
13 Correct 521 ms 198768 KB Output is correct
14 Correct 496 ms 198728 KB Output is correct
15 Correct 520 ms 198828 KB Output is correct
16 Correct 237 ms 163264 KB Output is correct

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3664 KB Output is correct
2 Correct 2 ms 3664 KB Output is correct
3 Correct 9 ms 8016 KB Output is correct
4 Correct 8 ms 6844 KB Output is correct
5 Correct 8 ms 7504 KB Output is correct
6 Correct 13 ms 10320 KB Output is correct
7 Correct 7 ms 6480 KB Output is correct
8 Correct 2 ms 3664 KB Output is correct
9 Correct 9 ms 8016 KB Output is correct
10 Correct 9 ms 8004 KB Output is correct
11 Correct 9 ms 8156 KB Output is correct
12 Correct 9 ms 8016 KB Output is correct
13 Correct 10 ms 8016 KB Output is correct
14 Correct 6 ms 6224 KB Output is correct
15 Correct 2 ms 3832 KB Output is correct
16 Correct 691 ms 185260 KB Output is correct
17 Execution timed out 3705 ms 2082340 KB Time limit exceeded
18 Halted 0 ms 0 KB -