oj.uz

Submission #1087729

# Submission time Handle Problem Language Result Execution time Memory
1087729 2024-09-13T07:11:49 Z mychecksedad Petrol stations (CEOI24_stations) C++17
0 / 100
 166 ms 14248 KB 
#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];
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 = f3(v, p, par[v], dist[p] - dist[v], 0ll);
			pd[up] += pd[v] + num;
			PD[up] += (pd[v] + num) * s[up2];
		}else{
			pd[up] += dp[v];
			PD[up] += 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){
		cout << (dp[i] - 1) * (n - s[i]) + PD[i] << '\n';
	}
}

int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	solve();
	return 0;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #1
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 5 ms 4444 KB Output is correct
4 Correct 13 ms 4592 KB Output is correct
5 Incorrect 3 ms 4444 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 35 ms 14248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 35 ms 14248 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 166 ms 9440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 166 ms 9440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 5 ms 4444 KB Output is correct
4 Correct 13 ms 4592 KB Output is correct
5 Incorrect 3 ms 4444 KB Output isn't correct
6 Halted 0 ms 0 KB -