oj.uz

Submission #1106073

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

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;
    };
    long long n = 0, shift = 0;
    int 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, long long l, long long r, long long i, int x) {
        if (l > i || r <= i) return;
        if (l + 1 == r) {
            t[p].val += x;
            return;
        }
        long long 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, long long l, long long r, long long a, long long b) {
        if (l >= b || r <= a || t[p].val == 0) return 0;
        if (a <= l && r <= b) return t[p].val;
        long long 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(long long _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 long long inf = 1'000'000'000'000'000;

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

void calc_sz(int v, int p, long long 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 592 KB Output is correct
4 Correct 18 ms 544 KB Output is correct
5 Correct 10 ms 592 KB Output is correct
6 Correct 20 ms 848 KB Output is correct
7 Correct 19 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 12 ms 592 KB Output is correct
10 Correct 12 ms 640 KB Output is correct
11 Correct 19 ms 592 KB Output is correct
12 Correct 13 ms 592 KB Output is correct
13 Correct 15 ms 592 KB Output is correct
14 Correct 4 ms 336 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 2318 ms 11792 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 2318 ms 11792 KB Output is correct
5 Correct 2988 ms 61592 KB Output is correct
6 Execution timed out 3561 ms 61596 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 1994 ms 6472 KB Output is correct
4 Correct 2338 ms 12184 KB Output is correct
5 Correct 2418 ms 11336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1854 ms 6968 KB Output is correct
8 Correct 1910 ms 7116 KB Output is correct
9 Correct 1838 ms 7100 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 1994 ms 6472 KB Output is correct
4 Correct 2338 ms 12184 KB Output is correct
5 Correct 2418 ms 11336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1854 ms 6968 KB Output is correct
8 Correct 1910 ms 7116 KB Output is correct
9 Correct 1838 ms 7100 KB Output is correct
10 Correct 961 ms 7492 KB Output is correct
11 Correct 1262 ms 6728 KB Output is correct
12 Correct 1311 ms 6912 KB Output is correct
13 Correct 1375 ms 6728 KB Output is correct
14 Correct 1306 ms 6916 KB Output is correct
15 Correct 1340 ms 6912 KB Output is correct
16 Correct 257 ms 6844 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 592 KB Output is correct
4 Correct 18 ms 544 KB Output is correct
5 Correct 10 ms 592 KB Output is correct
6 Correct 20 ms 848 KB Output is correct
7 Correct 19 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 12 ms 592 KB Output is correct
10 Correct 12 ms 640 KB Output is correct
11 Correct 19 ms 592 KB Output is correct
12 Correct 13 ms 592 KB Output is correct
13 Correct 15 ms 592 KB Output is correct
14 Correct 4 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 2318 ms 11792 KB Output is correct
17 Correct 2988 ms 61592 KB Output is correct
18 Execution timed out 3561 ms 61596 KB Time limit exceeded
19 Halted 0 ms 0 KB -