oj.uz

Submission #1106071

# Submission time Handle Problem Language Result Execution time Memory
1106071 2024-10-29T07:05:40 Z Semen07 Petrol stations (CEOI24_stations) C++17
55 / 100
 3500 ms 115352 KB 
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define int long long

using namespace std;

template<typename T>
istream &operator>>(istream &in, vector<T> &v) {
    for (auto &u: v) in >> u;
    return in;
}

class SegTree {
    struct node {
        int val = 0;
        int left = -1, right = -1;
        node() = default;
    };
    int n = 0, shift = 0, root = -1;;
    vector<node> t;
    int create() {
        t.emplace_back();
        return (int)t.size() - 1;
    }
    void push(int p) {
        if (t[p].left == -1) t[p].left = create();
        if (t[p].right == -1) t[p].right = create();
    }
    void add(int p, int l, int r, int i, int x) {
        if (l > i || r <= i) return;
        if (l + 1 == r) {
            t[p].val += x;
            return;
        }
        int mid = (l + r) / 2; push(p);
        add(t[p].left, l, mid, i, x);
        add(t[p].right, mid, r, i, x);
        t[p].val = t[t[p].left].val + t[t[p].right].val;
    }
    int get(int p, int l, int r, int a, int b) {
        if (l >= b || r <= a || t[p].val == 0) return 0;
        if (a <= l && r <= b) return t[p].val;
        int mid = (l + r) / 2; push(p);
        return get(t[p].left, l, mid, a, b) + get(t[p].right, mid, r, a, b);
    }
 public:
    void assign(int _n) {
        n = _n;
        t.clear();
        root = create();
    }
    SegTree() = default;
    void add(int i, int x) {
        add(root, 0, n, i + shift, x);
    }
    int get(int l, int r) {
        return get(root, 0, n, l + shift, r + shift);
    }
    void make_shift(int x) {
        shift += x;
    }
};

constexpr int inf = 1'000'000'000'000'000;

int n, k;
vector<vector<pair<int, int>>> g;
vector<int> res, used, sz, w, st, cnt;
SegTree d;

void calc_sz(int v, int p, int wt) {
    sz[v] = 1;
    w[v] = wt;
    for (auto [u, c]: g[v]) {
        if (u == p || used[u]) continue;
        calc_sz(u, v, wt + c);
        sz[v] += sz[u];
    }
}

int find_centroid(int v, int p, int full) {
    for (auto [u, c]: g[v]) {
        if (u == p || used[u]) continue;
        if (2 * sz[u] > full) return find_centroid(u, v, full);
    }
    return v;
}

void first_dfs(int v, int p, int paths, bool flag) {
    st.push_back(v);
    cnt[v] = 0;
    for (auto [u, c]: g[v]) {
        if (u == p || used[u]) continue;
        first_dfs(u, v, paths, flag);
    }
    int l = -1, r = (int)st.size();
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (w[v] - w[st[mid]] > k) l = mid;
        else r = mid;
    }
    if (r == 0) d.add(k - w[v], cnt[v] + 1);
    else cnt[st[r]] += cnt[v] + 1;
    if (flag) res[v] += cnt[v] * paths;
    st.pop_back();
}

void second_dfs(int v, int p) {
    for (auto [u, c]: g[v]) {
        if (u == p || used[u]) continue;
        int sm = d.get(0, c);
        res[v] += sm * sz[u];
        d.add(k, sm);
        d.make_shift(c);
        second_dfs(u, v);
        d.make_shift(-c);
        d.add(k, -sm);
    }
}

void build_centroid(int v) {
    calc_sz(v, v, 0);
    int cent = find_centroid(v, v, sz[v]);
    calc_sz(cent, cent, 0);
    used[cent] = 1;

    st = {cent};

    d.assign(inf);
    for (int i = 0; i < (int)g[cent].size(); ++i) {
        auto [u, c] = g[cent][i];
        if (used[u]) continue;
        int sm = d.get(0, c);
        res[cent] += sm * sz[u];
        d.add(k, sm + 1);
        d.make_shift(c);
        second_dfs(u, cent);
        d.make_shift(-c);
        d.add(k, -sm - 1);
        first_dfs(u, cent, sz[cent] - sz[u], true);
    }

    st = {cent};

    d.assign(inf);
    for (int i = (int)g[cent].size() - 1; i >= 0; --i) {
        auto [u, c] = g[cent][i];
        if (used[u]) continue;
        int sm = d.get(0, c);
        res[cent] += sm * sz[u];
        d.add(k, sm);
        d.make_shift(c);
        second_dfs(u, cent);
        d.make_shift(-c);
        d.add(k, -sm);
        first_dfs(u, cent, sz[cent] - sz[u], false);
    }

    for (auto [u, c]: g[cent]) {
        if (!used[u]) build_centroid(u);
    }
}

void solve() {
    cin >> n >> k;
    g.assign(n, {});
    for (int _ = 0; _ < n - 1; ++_) {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].emplace_back(v, c);
        g[v].emplace_back(u, c);
    }
    res.assign(n, 0);
    used.assign(n, 0);
    sz.assign(n, 0);
    w.assign(n, 0);
    cnt.assign(n, 0);
    st.clear();
    build_centroid(0);
    for (int i = 0; i < n; ++i) {
        cout << res[i] << '\n';
    }
    cout << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int _t = 1;
#ifdef LOCAL
    freopen("io/main.in", "r", stdin);
    freopen("io/main.out", "w", stdout);
    cin >> _t;
#endif
    while (_t--) solve();
}

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 13 ms 708 KB Output is correct
4 Correct 17 ms 592 KB Output is correct
5 Correct 9 ms 592 KB Output is correct
6 Correct 19 ms 1040 KB Output is correct
7 Correct 18 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 12 ms 756 KB Output is correct
10 Correct 12 ms 760 KB Output is correct
11 Correct 13 ms 760 KB Output is correct
12 Correct 14 ms 592 KB Output is correct
13 Correct 12 ms 776 KB Output is correct
14 Correct 4 ms 592 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2264 ms 17200 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 1 ms 336 KB Output is correct
4 Correct 2264 ms 17200 KB Output is correct
5 Correct 2996 ms 115100 KB Output is correct
6 Execution timed out 3549 ms 115352 KB Time limit exceeded
7 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 1889 ms 9708 KB Output is correct
4 Correct 2324 ms 17584 KB Output is correct
5 Correct 3059 ms 14800 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1704 ms 9104 KB Output is correct
8 Correct 1820 ms 10176 KB Output is correct
9 Correct 1709 ms 9988 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 1889 ms 9708 KB Output is correct
4 Correct 2324 ms 17584 KB Output is correct
5 Correct 3059 ms 14800 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1704 ms 9104 KB Output is correct
8 Correct 1820 ms 10176 KB Output is correct
9 Correct 1709 ms 9988 KB Output is correct
10 Correct 964 ms 10568 KB Output is correct
11 Correct 1212 ms 8720 KB Output is correct
12 Correct 1254 ms 9644 KB Output is correct
13 Correct 1296 ms 9488 KB Output is correct
14 Correct 1250 ms 9488 KB Output is correct
15 Correct 1318 ms 9676 KB Output is correct
16 Correct 240 ms 10168 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 13 ms 708 KB Output is correct
4 Correct 17 ms 592 KB Output is correct
5 Correct 9 ms 592 KB Output is correct
6 Correct 19 ms 1040 KB Output is correct
7 Correct 18 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 12 ms 756 KB Output is correct
10 Correct 12 ms 760 KB Output is correct
11 Correct 13 ms 760 KB Output is correct
12 Correct 14 ms 592 KB Output is correct
13 Correct 12 ms 776 KB Output is correct
14 Correct 4 ms 592 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 2264 ms 17200 KB Output is correct
17 Correct 2996 ms 115100 KB Output is correct
18 Execution timed out 3549 ms 115352 KB Time limit exceeded
19 Halted 0 ms 0 KB -