Submission #1220953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220953		KindaGoodGames	Petrol stations (CEOI24_stations)	C++20	18 / 100	3594 ms	10244 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int,int>
#define tiii tuple<int,int,int>

vector<vector<pii>> adj;
int n, k;
vector<int>ans;

void DFS(int v, int p, int c, vector<int>& sz){ 
    for(auto t : adj[v]){
        int u,l;
        tie(u,l) = t;
        if(u == p) continue;

        if(c-l < 0) {
            ans[v]+=sz[u];
            DFS(u,v,k-l, sz);
        }else{
            DFS(u,v,c-l,sz);
        }
    }
}
void DFSsz(int v, int p, vector<int>& sz){
    sz[v] = 1;
    for(auto t : adj[v]){
        int u,l;
        tie(u,l) = t;
        if(u == p) continue; 

        DFSsz(u,v, sz); 
        sz[v] += sz[u];
    }
}

int32_t main(){
    cin >> n >> k; 

    adj.resize(n); 
    ans.resize(n); 

    for(int i = 0; i < n-1; i++){
        int a,b,c;
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    for(int i = 0; i < n; i++){
        vector<int> sz(n);
        DFSsz(i,i,sz);
        DFS(i,i,k,sz);
    }

    for(int i = 0; i < n; i++){
        cout << ans[i] << endl;
    }
}

• 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