oj.uz

Submission #1053205

# Submission time Handle Problem Language Result Execution time Memory
1053205 2024-08-11T09:44:19 Z elazarkoren Petrol stations (CEOI24_stations) C++17
18 / 100
 3500 ms 11608 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 1e5 + 5;

ll ans[MAX_N];
vii tree[MAX_N];
ll sz[MAX_N];
int n, k;

int DfsSz(int node, int parent) {
    sz[node] = 1;
    for (auto [neighbor, w] : tree[node]) {
        if (neighbor != parent) {
            sz[node] += DfsSz(neighbor, node);
        }
    }
    return sz[node];
}

void Solve(int node, int parent, int d) {
    for (auto [neighbor, w] : tree[node]) {
        if (neighbor == parent) continue;
        if (d < w) {
            ans[node] += sz[neighbor];
            Solve(neighbor, node, k - w);
        } else Solve(neighbor, node, d - w);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int u, v, l;
        cin >> u >> v >> l;
        tree[u].push_back({v, l});
        tree[v].push_back({u, l});
    }
    for (int i = 0; i < n; i++) {
        DfsSz(i, -1);
        Solve(i, -1, k);
    }
    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 1 ms 3416 KB Output is correct
2 Correct 1 ms 3160 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3160 KB Output is correct
3 Correct 8 ms 3420 KB Output is correct
4 Correct 16 ms 3464 KB Output is correct
5 Correct 10 ms 3420 KB Output is correct
6 Correct 21 ms 3532 KB Output is correct
7 Correct 18 ms 3420 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 10 ms 3420 KB Output is correct
10 Correct 10 ms 3416 KB Output is correct
11 Correct 10 ms 3480 KB Output is correct
12 Correct 11 ms 3420 KB Output is correct
13 Correct 10 ms 3420 KB Output is correct
14 Correct 9 ms 3420 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Execution timed out 3581 ms 11608 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3160 KB Output is correct
3 Correct 1 ms 3160 KB Output is correct
4 Execution timed out 3581 ms 11608 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3160 KB Output is correct
3 Execution timed out 3559 ms 7260 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3160 KB Output is correct
3 Execution timed out 3559 ms 7260 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3160 KB Output is correct
3 Correct 8 ms 3420 KB Output is correct
4 Correct 16 ms 3464 KB Output is correct
5 Correct 10 ms 3420 KB Output is correct
6 Correct 21 ms 3532 KB Output is correct
7 Correct 18 ms 3420 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 10 ms 3420 KB Output is correct
10 Correct 10 ms 3416 KB Output is correct
11 Correct 10 ms 3480 KB Output is correct
12 Correct 11 ms 3420 KB Output is correct
13 Correct 10 ms 3420 KB Output is correct
14 Correct 9 ms 3420 KB Output is correct
15 Correct 1 ms 3160 KB Output is correct
16 Execution timed out 3581 ms 11608 KB Time limit exceeded
17 Halted 0 ms 0 KB -