Submission #1170809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170809		WH8	Petrol stations (CEOI24_stations)	C++20	0 / 100	92 ms	14780 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
 
#define pb push_back
#define int long long 
#define f first
#define s second
#define pll pair<long long, long long>
vector<vector<pll>> al(70005);
int oti[70005];
vector<pair<int,int>> ord;

void dfs(int x,int p){
	for(auto [it,di]:al[x]){
		if(it==p)continue;
		ord.pb({it, di});
		dfs(it, x);
	}
}
signed main(){
	int n,k;cin>>n>>k;
	for(int i=0;i<n-1;i++){
		int a,b,l;cin>>a>>b>>l;
		al[a].pb({b,l});
		al[b].pb({a,l});
	}
	int cur=0;
	for(int i=0;i<n-1;i++){
		if(al[i].size()==1)cur=i;
	}
	ord.pb({cur, 0});
	dfs(cur,-1);
	int ans[n]; fill(ans, ans+n,0);
	
	queue<pair<int,int>> q;
	q.push({k,1});
	int os=0;
	for(int i=0;i<n;i++){
		oti[i]=ord[i].f;
	}
	//~ for(int i=0;i<n;i++){
		//~ cout<<ord[i].f<<" "<<ord[i].s<<endl;
		//~ cout<<oti[i]<<endl;
	//~ }
	
	for(int i=1;i<=n-2;i++){
		os-=ord[i].s;
		int sm=0;
		while(!q.empty() and q.front().f+os<ord[i+1].s){
			sm+=q.front().s;
			q.pop();
		}
		ans[i]+=(sm*(n-i-1));
		q.push({k-os,sm+1});
		//~ printf("i is %lld, os is %lld, ord[i+1].s is %lld, sm is %lld\n",i,os,ord[i+1].s, sm);

	}
	
	os=0;
	while(!q.empty())q.pop();
	q.push({k,1});
	for(int i=n-2;i>=1;i--){
		os-=ord[i+1].s;
		int sm=0;
		while(!q.empty() and q.front().f+os<ord[i].s){
			sm+=q.front().s;
			q.pop();
		}
		ans[i]+=(sm*(i));
		q.push({k-os,sm+1});
	}
	for(int i=0;i<n;i++){
		cout<<ans[oti[i]]<<endl;
	}
	
}

• 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