제출 #1290046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290046		loom	Petrol stations (CEOI24_stations)	C++20	37 / 100	47 ms	24156 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)2e18
#define nl '\n'

const int N = 7e4, K = 11;
vector<pair<int,int>> g[N];
int up[N][K], dn[N][K];
int ans[N], sz[N];
int n, k;

void dfs1(int v, int p){
   up[v][k]++;
   sz[v] = 1;

   for(auto &[ch, w] : g[v]){
      if(ch == p) continue;

      dfs1(ch, v);
      sz[v] += sz[ch];

      for(int i = 0; i <= k; i++){
         int c = up[ch][i];

         if(i < w) up[v][k - w] += c;
         else up[v][i - w] += c;
      }
   }
}

void dfs2(int v, int p){
   for(int i = 0; i <= k; i++) dn[v][i] += up[v][i];

   for(auto &[ch, w] : g[v]){
      if(ch == p) continue;

      for(int i = 0; i <= k; i++){
         if(i < w) dn[v][k - w] -= up[ch][i];
         else dn[v][i - w] -= up[ch][i];
      }
      
      for(int i = 0; i <= k; i++){
         if(i < w) ans[ch] += up[ch][i] * (n - sz[ch]);
         int c = dn[v][i];

         if(i < w){
            ans[v] += c * sz[ch];
            dn[ch][k - w] += c;
         }
         else{
            dn[ch][i - w] += c;
         }
      }

      dfs2(ch, v);

      for(int i = 0; i <= k; i++){
         if(i < w) dn[v][k - w] += up[ch][i];
         else dn[v][i - w] += up[ch][i];
      }
   }
}

void solve(){
   cin>>n>>k;

   for(int i = 1; i < n; i++){
      int x, y, w;
      cin>>x>>y>>w;

      g[x].push_back({y, w});
      g[y].push_back({x, w});
   }

   dfs1(0, -1);
   dfs2(0, -1);

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

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   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