Submission #1232140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232140		PVM_pvm	Petrol stations (CEOI24_stations)	C++20	18 / 100	3594 ms	10516 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define MAXN 70'007
int n,k;
vector<pair<int,int>> v[MAXN];
long long otg[MAXN];
int gol[MAXN];
void dfs_tr(int x, int par)
{
    gol[x]=1;
    for (int q=0;q<v[x].size();q++)
    {
        if (v[x][q].first==par) continue;
        dfs_tr(v[x][q].first,x);
        gol[x]+= gol[ v[x][q].first ];
    }
}
void dfs(int x, int par, int rez)
{
    for (int q=0;q<v[x].size();q++)
    {
        if (v[x][q].first==par) continue;
        if (rez<v[x][q].second)
        {
            otg[x]+=gol[ v[x][q].first ];
            dfs(v[x][q].first,x,k-v[x][q].second);
        }
        else
        {
            dfs(v[x][q].first,x,rez-v[x][q].second);
        }
    }
}
int main()
{
    cin>>n>>k;
    for (int q=0;q<n-1;q++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    for (int q=0;q<n;q++)
    {
        dfs_tr(q,-1);
        dfs(q,-1,k);
    }
    for (int q=0;q<n;q++) cout<<otg[q]<<"\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