Submission #1140626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140626		Jawad_Akbar_JJ	Petrol stations (CEOI24_stations)	C++20	18 / 100	67 ms	13248 KiB

Main

#include <iostream>
#include <vector>

using namespace std;
#define int long long
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[i];
			dfs2(i, u, k - w);
		}
		else
			dfs2(i, u, cap - w);
	}
}

vector<int> vec;
void get(int u, int p){
	vec.push_back(u);
	for (auto [i, j] : nei[u])
		if (i != p)
			get(i, u);
}

void solve2(){
	for (int i=1;i<=n;i++)
		ch[i] += ((i - 1) / k) * (n - i);
	
	for (int i=0;i<n;i++)
		if (nei[i].size() == 1 and vec.size() == 0)
			get(i, i);
	for (int i=1;i<=n;i++)
		Sum[vec[i-1]] = ch[i];
	for (int i=0;i<n;i++)
		cout<<Sum[i]<<'\n';
}

signed 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});
	}
	if (n <= 1000){
		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';
	}
	else
		solve2();
}

• 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