oj.uz

Submission #1053228

# Submission time Handle Problem Language Result Execution time Memory
1053228 2024-08-11T09:53:02 Z elazarkoren Petrol stations (CEOI24_stations) C++17
18 / 100
 34 ms 15448 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)
#define int ll
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

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);
//    }
//}

int32_t 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 start = 0; start < n; start++) {
        if (tree[start].size() != 1) continue;
        int node = start;
        vb visited(n);
        vi cnt(n);
        queue<pii> q;
        ll s1 = 0;
        for (int t = 0; t < n - 1; t++) {
            visited[node] = 1;
            int nx = -1, nw;
            for (auto [neighbor, w] : tree[node]) {
                if (!visited[neighbor]) {
                    nx = neighbor;
                    nw = w;
                }
            }
            q.push({node, s1});
            s1 += nw;
            while (!q.empty() && s1 - q.front().y > k) {
                cnt[node] += cnt[q.front().x];
                q.pop();
            }
            ans[node] += cnt[node] * ll(n - t - 1);
            cnt[node]++;
            node = nx;
        }
        cout << "";
    }
//    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';
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:70:16: warning: 'nw' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |             s1 += nw;
      |             ~~~^~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Runtime error 3 ms 6488 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 27 ms 8768 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 27 ms 8768 KB Output is correct
5 Correct 34 ms 8760 KB Output is correct
6 Correct 25 ms 10040 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Runtime error 19 ms 15448 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Runtime error 19 ms 15448 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Runtime error 3 ms 6488 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -