oj.uz

답안 #1087889

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1087889 2024-09-13T11:09:37 Z mychecksedad Petrol stations (CEOI24_stations) C++17
26 / 100
 3500 ms 14932 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], ex[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(u != p && ex[u] && u != v){
			f(u, v, up, parw);
		}
	}
}
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(u != p && ex[u] && u != v){
			f2(u, v, up, up2, parw, D+U.ss);
		}
	}
}

void merg(int a, int b, int pp){
	if(g[a].size() > g[b].size()) g[a].swap(g[b]);
	for(auto x: g[a]) g[b].pb(x);
	if(pp != b) {g[a].swap(g[b]);}
// cout << pp << endl;
// 	for(auto x: g[pp]) cout << x.ff << " "; en;
}

void dfs(int v, int p, ll parw){
	dp[v] = 1;
	s[v] = 1;
	par[v] = p;
	tin[v] = timer++;
	// if(v != 1 && parw == 0){
	// 	ex[v] = 0;
	// 	// cout << "merge: " << v << ' ' << p << endl;
	// 	merg(v, p, p);
	// 	return;
	// }
	for(int i = 0; i < g[v].size(); ++i){
		auto U = g[v][i];
		int u = U.ff;
		if(u != p && ex[u] && u != v && s[u] == 0){
			// cout << u << ' ' << v << endl;
			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 && ex[u] && u != v){
			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});
	}
	for(int i = 1; i <= n; ++i){
		ex[i] = 1;
		s[i] = 0;
	}
	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] << ' ';
	// }
	// for(int i = 1; i <= n; ++i) cout << dp[i] << ' ' << pd[i] << '\n';
	for(int i = 1; i <= n; ++i){
		if(ex[i] == 0){
			cout << "0\n";
			continue;
		}
		pdreal[i] = 0;
		for(auto U: g[i]){
			if(U.ff != par[i] && U.ff != i && ex[U.ff]) 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

Main.cpp: In function 'void f2(int, int, int, int, long long int, long long int)':
Main.cpp:39:7: warning: unused variable 'num' [-Wunused-variable]
   39 |    ll num = 0;
      |       ^~~
Main.cpp: In function 'void dfs(int, int, long long int)':
Main.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i = 0; i < g[v].size(); ++i){
      |                 ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 6 ms 2940 KB Output is correct
4 Correct 10 ms 2908 KB Output is correct
5 Correct 3 ms 2904 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 12 ms 2904 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 3 ms 2904 KB Output is correct
10 Correct 2 ms 2904 KB Output is correct
11 Correct 2 ms 2908 KB Output is correct
12 Correct 2 ms 2908 KB Output is correct
13 Correct 2 ms 2956 KB Output is correct
14 Correct 7 ms 2972 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 37 ms 14712 KB Output is correct

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 37 ms 14712 KB Output is correct
5 Correct 51 ms 14932 KB Output is correct
6 Execution timed out 3523 ms 12628 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 83 ms 10840 KB Output is correct
4 Correct 43 ms 14428 KB Output is correct
5 Execution timed out 3569 ms 13336 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 83 ms 10840 KB Output is correct
4 Correct 43 ms 14428 KB Output is correct
5 Execution timed out 3569 ms 13336 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 6 ms 2940 KB Output is correct
4 Correct 10 ms 2908 KB Output is correct
5 Correct 3 ms 2904 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 12 ms 2904 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 3 ms 2904 KB Output is correct
10 Correct 2 ms 2904 KB Output is correct
11 Correct 2 ms 2908 KB Output is correct
12 Correct 2 ms 2908 KB Output is correct
13 Correct 2 ms 2956 KB Output is correct
14 Correct 7 ms 2972 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 37 ms 14712 KB Output is correct
17 Correct 51 ms 14932 KB Output is correct
18 Execution timed out 3523 ms 12628 KB Time limit exceeded
19 Halted 0 ms 0 KB -