Submission #1087734

#TimeUsernameProblemLanguageResultExecution timeMemory
1087734mychecksedadPetrol stations (CEOI24_stations)C++17
26 / 100
3572 ms15188 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long int #define pb push_back #define en cout << '\n' #define vi vector<int> #define pii pair<int, int> #define ff first #define ss second #define all(x) x.begin(),x.end() const int N = 1e5+100; int n, k, tin[N], tout[N], timer = 0, par[N]; vector<pii> g[N]; ll dp[N], s[N], dist[N], pd[N], PD[N], pdreal[N]; bool is_ancestor(int u, int v){ return tin[u] <= tin[v] && tout[v] <= tout[u]; } void f(int v, int p, int up, ll parw){ // cout << v << ' ' << p << ' ' << up << ' ' << parw << ' ' << dist[v] << "f\n"; if(dist[v] - dist[up] > k) return; if(dist[v] - dist[up] <= k && dist[v] - dist[up] + parw > k){ // cout << "gh\n"; dp[up] += dp[v]; } for(auto U: g[v]){ int u = U.ff; if(p != u){ f(u, v, up, parw); } } } ll f3(int v, int p, int p2, ll parw, ll D){ ll num = 0; if(D > k) return num; if(D <= k && D + parw > k){ // cout << "gh\n"; num += dp[v]; } for(auto U: g[v]){ int u = U.ff; if(p != u && u != p2){ num += f3(u, v, p2, parw, D + U.ss); } } return num; } void f2(int v, int p, int up, int up2, ll parw, ll D){ // cout << v << ' ' << p << ' ' << up << ' ' << parw << ' ' << dist[v] << "f\n"; if(D > k) return; if(D <= k && D + parw > k){ if(is_ancestor(v, up)){ ll num = 0; // cout << v << " : " << up << '\n'; // ll num = f3(v, p, par[v], dist[p] - dist[v], 0ll); pd[up2] += pd[p]; PD[up2] += pd[p] * s[up2]; }else{ // cout << v << ':' << up << '\n'; pd[up2] += dp[v]; PD[up2] += dp[v] * s[up2]; } } for(auto U: g[v]){ int u = U.ff; if(p != u){ f2(u, v, up, up2, parw, D+U.ss); } } } void dfs(int v, int p, ll parw){ dp[v] = 1; s[v] = 1; par[v] = p; tin[v] = timer++; for(auto U: g[v]){ int u = U.ff; if(u != p){ dist[u] = dist[v] + U.ss; dfs(u, v, U.ss); s[v] += s[u]; } } tout[v] = timer++; f(v, p, v, parw); } void dfs2(int v, int p, ll parw){ pd[v] = 1; PD[v] = 0; if(p != v) f2(p, v, p, v, parw, 0ll); for(auto U: g[v]){ int u = U.ff; if(u != p){ dfs2(u, v, U.ss); } } } void solve(){ cin >> n >> k; for(int i = 1; i < n; ++i){ int u, v, w; cin >> u >> v >> w; ++u, ++v; g[u].pb({v, w}); g[v].pb({u, w}); } dfs(1, 1, 0); // for(int i = 1; i <= n; ++i){ // cout << dp[i] << ' '; // } dfs2(1, 1, 0); // for(int i = 1; i <= n; ++i) cout << dp[i] << ' ' << pd[i] << '\n'; for(int i = 1; i <= n; ++i){ pdreal[i] = 0; for(auto U: g[i]){ if(U.ff != par[i]) pdreal[i] += PD[U.ff]; } cout << (dp[i] - 1) * (n - s[i]) + pdreal[i] << '\n'; } } int main(){ cin.tie(0); ios::sync_with_stdio(0); solve(); return 0; }

Compilation message (stderr)

Main.cpp: In function 'void f2(int, int, int, int, long long int, long long int)':
Main.cpp:54:7: warning: unused variable 'num' [-Wunused-variable]
   54 |    ll num = 0;
      |       ^~~
#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...