oj.uz

Submission #25637

# Submission time Handle Problem Language Result Execution time Memory
25637 2017-06-23T10:05:38 Z szawinis Uzastopni (COCI15_uzastopni) C++14
0 / 160
 0 ms 1844 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX = (5e5)+1;

int n, k, sum[MAX];
long long dp[MAX], mxp[MAX], ans[MAX];
pair<long long, int> l[MAX][2];
vector<pair<int,int> > g[MAX];
bool need[MAX];

void dfs1(int u, int par) {
	sum[u] = need[u];
	for(auto p: g[u]) {
		int v, w;
		tie(v, w) = p;
		if(v != par) {
			dfs1(v, u);
			sum[u] += sum[v];
			if(!sum[v]) continue;
			dp[u] += dp[v] + 2*w;
			if(l[v][0].first + w > l[u][0].first) {
				l[u][1] = l[u][0];
				l[u][0] = {l[v][0].first + w, v};
			} else if(l[v][0].first + w > l[u][1].first) {
				l[u][1] = {l[v][0].first + w, v};
			}
		}
	}
}

void dfs2(int u, int par, long long up = 0) {
	ans[u] = up + dp[u] - max(mxp[u], l[u][0].first);
	for(auto p: g[u]) {
		int v, w;
		tie(v, w) = p;
		if(v != par) {
			long long tmp = (v == l[u][0].second ? l[u][1].first : l[u][0].first);
			mxp[v] = max((tmp || sum[u] - sum[v])*(tmp + w), bool(mxp[u])*(mxp[u] + w));
			dfs2(v, u, up + (up || sum[u] - sum[v])*(dp[u] - dp[v] + !bool(sum[v])*2*w));
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for(int i = 1, u, v, w; i < n; i++) {
		cin >> u >> v >> w;
		g[u-1].emplace_back(v-1, w);
		g[v-1].emplace_back(u-1, w);
	}
	for(int i = 0, v; i < k; i++) cin >> v, need[v-1] = true;
	dfs1(0, -1);
	dfs2(0, -1);
	for(int i = 0; i < n; i++) cout << ans[i] << '\n';
}

Subtask #1
0 / 160.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)