Submission #1233654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233654		sophiaeternalia	Petrol stations (CEOI24_stations)	C++20	18 / 100	3593 ms	11744 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int int64_t

vector<vector<pair<int, int>>> g;
vector<int> r;
int k;

int dfs(int v, int la, int di){
    int s=0;
    for (auto u: g[v]){
        if (u.first!=la){
            int a;
            if (di+u.second>k){
                a=dfs(u.first, v, u.second);
                r[v]+=a;
            } else {
                a=dfs(u.first, v, di+u.second);
            }
            s+=a;
        }
    }
    return s+1;
}

signed main(){
    cin.tie(0); ios_base::sync_with_stdio(NULL);

    int n;
    cin>>n>>k;
    g.resize(n);
    for (int i=0; i<n-1; i++){
        int u, v, l;
        cin>>u>>v>>l;
        g[u].push_back({v, l});
        g[v].push_back({u, l});
    }
    r.assign(n, 0);
    for (int i=0; i<n; i++){
        dfs(i, -1, 0);
        /*for (auto u: r){
            cout<<u<<" ";
        }
        cout<<"\n";*/
    }
    for (auto u: r){
        cout<<u<<"\n";
    }
}

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