Submission #1140651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140651		KaleemRazaSyed	Petrol stations (CEOI24_stations)	C++20	18 / 100	3593 ms	10432 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 70000 + 10, K = 10 + 10;
vector<pair<int,int> > G[N], path;
ll ans[N];
int n, k;

void dfs(int v, int p = 0, int W = 0)
{
  path.push_back({v, W});
  for(auto [u, w] : G[v])
    if(u != p) dfs(u, v, w);
}

void evaluate()
{
  int cnt[n] = {}, j = 1;
  int sm = k;
  
  for(int i = 0; i + 1 < n; i ++)
    {
      while(j < path.size() && sm - path[j].second >= 0)
	sm -= path[j].second, j++;

      if(j < path.size())
	cnt[j - 1] += cnt[i] + 1;

      sm += path[i + 1].second;
    }
  

  cnt[n - 1] = 0;
  for(int i = 0; i < n; i ++)
    ans[path[i].first] += 1ll * (n - i - 1) * (cnt[i]);
}

int main()
{
  cin >> n >> k;
  for(int i = 1; i < n; i ++)
    {
      int u, v, w;
      cin >> u >> v >> w;
      G[u].push_back({v, w});
      G[v].push_back({u, w});
    }

  for(int i = 0; i < n; i ++)
    if(G[i].size() == 1) {
      dfs(i);
      evaluate();
      path.clear();
    }

  for(int i = 0; i < n; i ++)
    cout << ans[i] << endl;
    
  return 0;
}

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