Submission #1140508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140508		KaleemRazaSyed	Petrol stations (CEOI24_stations)	C++20	55 / 100	2642 ms	2162688 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];
ll ans[N], b[N][K];
map<int, ll> cnt[N];

int n, k, sz[N];

void dfs(int v, int p = 0)
{
  sz[v] = 1;
  for(auto [u, w] : G[v])
    {
      if(u == p) continue;

      dfs(u, v);
      sz[v] += sz[u];
      for(auto [pt, c] : cnt[u])
	{
	  if(pt < w)
	    {
	      cnt[v][k - w] += c;
	      ans[u] += 1ll * c * (n - sz[u]);
	    }
	  else
	    cnt[v][pt - w] += c;
	}
      
    }
  cnt[v][k] += 1;
}

void dfs2(int v, int p = 0)
{
  for(auto [u, w] : G[v])
    {
      if(u == p) continue;

      // remove the u part from my cnt
      for(auto [pt, c] : cnt[u])
	{
	  if(pt < w)
	    cnt[v][k - w] -= c;
	  else
	    cnt[v][pt - w] -= c;
	}
      

      // Adding how much will be added to the answer of u
      for(auto [pt, c] : cnt[v])
	if(pt < w)
	  ans[v] += 1ll * c * sz[u];

      // Add v to u
      for(auto [pt, c] : cnt[v])
	{
	  if(pt < w)
	    cnt[u][k - w] += c;
	  else
	    cnt[u][pt - w] += c;
	}

      dfs2(u, v);

     for(auto [pt, c] : cnt[v])
	{
	  if(pt < w)
	    cnt[u][k - w] -= c;
	  else
	    cnt[u][pt - w] -= c;
	}

     for(auto [pt, c] : cnt[u])
	{
	  if(pt < w)
	    cnt[v][k - w] += c;
	  else
	    cnt[v][pt - w] += c;
	}
      
      
    }
}

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});
    }

  dfs(0);
  dfs2(0);

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

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