Submission #1140505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140505		KaleemRazaSyed	Petrol stations (CEOI24_stations)	C++20	37 / 100	138 ms	22328 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 cnt[N][K], ans[N], b[N][K];
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(int i = 0; i < w; i++)
	{
	  cnt[v][k - w] += cnt[u][i];
	  ans[u] += 1ll * cnt[u][i] * (n - sz[u]);
	}
      for(int i = w; i <= k; i++)
	cnt[v][i - w] += cnt[u][i]; 
      
    }
  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(int i = 0; i < w; i++)
	cnt[v][k - w] -= cnt[u][i];

      for(int i = w; i <= k; i++)
	cnt[v][i - w] -= cnt[u][i];

      // Adding how much will be added to the answer of u
      for(int i = 0; i < w; i ++)
	ans[v] += 1ll * cnt[v][i] * sz[u];

      // Add v to u
      for(int i = 0; i < w; i++)
	cnt[u][k - w] += cnt[v][i];

      for(int i = w; i <= k; i++)
	cnt[u][i - w] += cnt[v][i];

      dfs2(u, v);

      for(int i = 0; i < w; i++)
	cnt[u][k - w] -= cnt[v][i];

      for(int i = w; i <= k; i++)
	cnt[u][i - w] -= cnt[v][i];

       for(int i = 0; i < w; i++)
	cnt[v][k - w] += cnt[u][i];

      for(int i = w; i <= k; i++)
	cnt[v][i - w] += cnt[u][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});
    }

  dfs(0);
  dfs2(0);

  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: 0 / 10
• Subtask 4: 12 / 12
• Subtask 5: 17 / 17
• Subtask 6: 0 / 35