Submission #1053224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053224		elazarkoren	Petrol stations (CEOI24_stations)	C++17	8 / 100	28 ms	11864 KiB

Main

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

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 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 (stderr)

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

• Subtask 0: 0 / 0
• Subtask 1: 0 / 18
• Subtask 2: 8 / 8
• Subtask 3: 0 / 10
• Subtask 4: 0 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35