Submission #1045824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045824		gagik_2007	Petrol stations (CEOI24_stations)	C++17	18 / 100	3569 ms	11736 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=70007;
ll n,m,k;
int sz[N];
vector<pair<int,ll>>g[N];
int ans[N];

void calcsz(int v, int par){
    sz[v]=1;
    for(auto e:g[v]){
        int to=e.ff;
        if(to!=par){
            calcsz(to,v);
            sz[v]+=sz[to];
        }
    }
}

void dfs(int v, int par, ll cur){
    // cout<<"TAZA DFS"<<endl;
    for(auto e:g[v]){
        int to=e.ff;
        ll w=e.ss;
        // cout<<"dfs: "<<v<<" "<<par<<" "<<cur<<endl;
        // cout<<"edge: "<<to<<" "<<w<<endl;
        if(to!=par){
            if(cur+w>k){
                // cout<<to<<" "<<cur<<endl;
                ans[v]+=sz[to];
                dfs(to,v,w);
            }
            else{
                dfs(to,v,cur+w);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("Einput.txt","r",stdin);
    // freopen("Eoutput.txt","w",stdout);
    cin>>n>>k;
    for(int i=0;i<n-1;i++){
        int u,v;
        ll w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for(int v=0;v<n;v++){
        // cout<<"root: "<<v<<endl;
        calcsz(v,-1);
        dfs(v,-1,0);
    }
    for(int v=0;v<n;v++){
        cout<<ans[v]<<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