oj.uz

Submission #1100720

# Submission time Handle Problem Language Result Execution time Memory
1100720 2024-10-14T13:54:51 Z not_amir Petrol stations (CEOI24_stations) C++17
55 / 100
 3500 ms 2027912 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) + 1;
    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 3 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 3 ms 3664 KB Output is correct
2 Correct 2 ms 3664 KB Output is correct
3 Correct 10 ms 8016 KB Output is correct
4 Correct 8 ms 6736 KB Output is correct
5 Correct 9 ms 7576 KB Output is correct
6 Correct 14 ms 10332 KB Output is correct
7 Correct 7 ms 6224 KB Output is correct
8 Correct 2 ms 3664 KB Output is correct
9 Correct 13 ms 8016 KB Output is correct
10 Correct 12 ms 8016 KB Output is correct
11 Correct 9 ms 8272 KB Output is correct
12 Correct 12 ms 8016 KB Output is correct
13 Correct 9 ms 8068 KB Output is correct
14 Correct 7 ms 6224 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
0.0 / 10.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3664 KB Output is correct
2 Correct 2 ms 3664 KB Output is correct
3 Correct 640 ms 186644 KB Output is correct
4 Correct 825 ms 232752 KB Output is correct
5 Correct 660 ms 182716 KB Output is correct
6 Correct 2 ms 3664 KB Output is correct
7 Correct 606 ms 210196 KB Output is correct
8 Correct 609 ms 210188 KB Output is correct
9 Correct 620 ms 210244 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3664 KB Output is correct
2 Correct 2 ms 3664 KB Output is correct
3 Correct 640 ms 186644 KB Output is correct
4 Correct 825 ms 232752 KB Output is correct
5 Correct 660 ms 182716 KB Output is correct
6 Correct 2 ms 3664 KB Output is correct
7 Correct 606 ms 210196 KB Output is correct
8 Correct 609 ms 210188 KB Output is correct
9 Correct 620 ms 210244 KB Output is correct
10 Correct 457 ms 188236 KB Output is correct
11 Correct 455 ms 187208 KB Output is correct
12 Correct 522 ms 177808 KB Output is correct
13 Correct 523 ms 198940 KB Output is correct
14 Correct 486 ms 198728 KB Output is correct
15 Correct 493 ms 198728 KB Output is correct
16 Correct 222 ms 163260 KB Output is correct

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3664 KB Output is correct
2 Correct 2 ms 3664 KB Output is correct
3 Correct 10 ms 8016 KB Output is correct
4 Correct 8 ms 6736 KB Output is correct
5 Correct 9 ms 7576 KB Output is correct
6 Correct 14 ms 10332 KB Output is correct
7 Correct 7 ms 6224 KB Output is correct
8 Correct 2 ms 3664 KB Output is correct
9 Correct 13 ms 8016 KB Output is correct
10 Correct 12 ms 8016 KB Output is correct
11 Correct 9 ms 8272 KB Output is correct
12 Correct 12 ms 8016 KB Output is correct
13 Correct 9 ms 8068 KB Output is correct
14 Correct 7 ms 6224 KB Output is correct
15 Correct 2 ms 3664 KB Output is correct
16 Correct 737 ms 185260 KB Output is correct
17 Execution timed out 3704 ms 2027912 KB Time limit exceeded
18 Halted 0 ms 0 KB -