Submission #1193539

#TimeUsernameProblemLanguageResultExecution timeMemory
1193539UnforgettableplPetrol stations (CEOI24_stations)C++20
55 / 100
57 ms22856 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,K; cin >> N >> K; vector<vector<pair<int,int>>> adj(N+1); for(int i=1;i<N;i++){ int u,v,c;cin>>u>>v>>c;u++;v++; adj[u].emplace_back(v,c); adj[v].emplace_back(u,c); } vector<int> ans(N+1); vector DP(N+1,vector<int>(K+1)); vector<int> subsize(N+1); { function<void(int,int)> dfs = [&](int x,int p){ subsize[x]=1; DP[x][K]=1; for(auto&[v,c]:adj[x])if(v!=p){ dfs(v,x); subsize[x]+=subsize[v]; for(int i=c;i<=K;i++){ DP[x][i-c]+=DP[v][i]; } for(int i=0;i<c;i++){ DP[x][K-c]+=DP[v][i]; } } }; dfs(1,-1); } { function<void(int,int)> dfs = [&](int x,int p){ int pedge = -1; for(auto&[v,c]:adj[x])if(v==p)pedge=c; if(p!=-1){ subsize[x]+=subsize[p]; for(int i=pedge;i<=K;i++){ DP[x][i-pedge]+=DP[p][i]; } for(int i=0;i<pedge;i++){ DP[x][K-pedge]+=DP[p][i]; } } for(auto&[v,c]:adj[x]){ subsize[x]-=subsize[v]; for(int i=c;i<=K;i++){ DP[x][i-c]-=DP[v][i]; } for(int i=0;i<c;i++){ DP[x][K-c]-=DP[v][i]; } for(int i=0;i<c;i++){ ans[x]+=DP[x][i]*subsize[v]; } if(v!=p)dfs(v,x); subsize[x]+=subsize[v]; for(int i=c;i<=K;i++){ DP[x][i-c]+=DP[v][i]; } for(int i=0;i<c;i++){ DP[x][K-c]+=DP[v][i]; } } if(p!=-1){ subsize[x]-=subsize[p]; for(int i=pedge;i<=K;i++){ DP[x][i-pedge]-=DP[p][i]; } for(int i=0;i<pedge;i++){ DP[x][K-pedge]-=DP[p][i]; } } }; dfs(1,-1); } for(int i=1;i<=N;i++)cout<<ans[i]<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...