제출 #1140581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140581		Jawad_Akbar_JJ	Petrol stations (CEOI24_stations)	C++20	0 / 100	3594 ms	9864 KiB

Main

#include <iostream>
#include <vector>

using namespace std;
const int N = 1e5 + 10;
vector<pair<int,int>> nei[N];
int Sum[N], ch[N], n, k;

void dfs1(int u, int p){
	ch[u] = 1;
	for (auto [i, w] : nei[u])
		if (i != p)
			dfs1(i, u), ch[u] += ch[i];
}

void dfs2(int u, int p, int cap){
	for (auto [i, w] : nei[u]){
		if (i == p) continue;
		if (w > cap)
			Sum[u] += ch[u] - 1, cap = k;
		dfs2(i, u, cap - w);
	}
}


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

	for (int i=1;i<n;i++){
		int a, b, c;
		cin>>a>>b>>c;

		nei[a].push_back({b, c});
		nei[b].push_back({a, c});
	}

	for (int i=0;i<n;i++)
		dfs1(i, i), dfs2(i, i, k);

	for (int i=1;i<=n;i++)
		cout<<Sum[i - 1]<<'\n';
}

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