Submission #1140639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140639		KaleemRazaSyed	Petrol stations (CEOI24_stations)	C++20	0 / 100	3593 ms	5568 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 = 0;
  int sm = k;
  
  for(int i = 0; i + 1 < n; i ++)
    {
      while(j + 1 < path.size() && sm - path[j + 1].second >= 0)
	j++, sm -= path[j].second;
      cnt[j] += cnt[i] + 1;
      // cerr << "cnt[" << i << "] = "<< cnt[i] << endl;
      sm += path[i + 1].second;
    }
  

  cnt[n - 1] = 0;
  // after computing the cnt
  for(int i = 0; i < n; i ++)
    {
      // cerr << path[i].first << ' ' << cnt[i] << ' ' << n - i - 1 << endl;
      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: 0 / 8
• Subtask 3: 0 / 10
• Subtask 4: 0 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35