제출 #1140631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140631		Jawad_Akbar_JJ	Petrol stations (CEOI24_stations)	C++20	26 / 100	59 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=1;i<=n;i++)
		Sum[i] = ch[i] + ch[n - i + 1];
	for (int i=1;i<=n;i++)
		ch[i] = Sum[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: 8 / 8
• Subtask 3: 0 / 10
• Subtask 4: 0 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35