Submission #1069830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069830		vjudge1	Petrol stations (CEOI24_stations)	C++17	18 / 100	3588 ms	6276 KiB

Main

#include <bits/stdc++.h>
#define div /
#define ll long long

#define fore(i, l, r) for(int i=int(l); i<int(r); i++)
#define sz(a) int((a).size())

using namespace std;

const int INF = 1e9;
const int MX = 5e5 + 23;
const int MOD = 1000000007;
const int MAX_N = 5e5+23;
const int N = 1e6;

int ans[70005],n,k;
vector<pair<int,int>>adj[70005];

int cnt(int s, int prev) {
    int brojac=1;
    for(auto u : adj[s]) {
        if(u.first != prev)
            brojac += cnt(u.first, s);
    }
    return brojac;
}

void dfs(int s, int fuel, int prev) {
    for(auto u : adj[s]) {
        if(u.first != prev and u.second <= fuel)
            dfs(u.first, fuel-u.second, s);
        else if(u.first != prev) {
            ans[s] += cnt(u.first, s);
            dfs(u.first, k-u.second, s);
        }
    }
}

void solve() {
    cin >> n >> k;
    fore(i,0,n-1) {
        int u,v,d;
        cin >> u >> v >> d;
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
    }
    fore(i,0,n)
        dfs(i,k,-1);
    fore(i,0,n)
        cout << ans[i] << endl;
}

int main() {
    ios::sync_with_stdio(false);

    int t=1;
    while(t--) solve();
}

• 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