oj.uz

Submission #200095

# Submission time Handle Problem Language Result Execution time Memory
200095 2020-02-05T10:21:28 Z Saboon Transport (COCI19_transport) C++14
130 / 130
 544 ms 17764 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5 + 10;

ll a[maxn];
vector<pair<int,int> > t[maxn];
bool mark[maxn];
vector<ll> DP, PD;
int sz[maxn], cent;
ll dp[maxn], pd[maxn], s[maxn];
ll answer = 0;

void dfs_add(int v, int par){
	PD.push_back(pd[v]);
	if (dp[v] >= 0)
		DP.push_back(s[v]);
	for (auto edge : t[v]){
		int u = edge.first;
		if (u == par or mark[u])
			continue;
		dfs_add(u, v);
	}
}

void dfs(int v, int par = -1){
	if (par != -1){
		if (dp[v] >= 0){
			ll me = s[v];
			int idx = upper_bound(PD.begin(), PD.end(), me) - PD.begin();
			answer += idx;
		}
		int siz = DP.size();
		int idx = lower_bound(DP.begin(), DP.end(), pd[v]) - DP.begin();
		answer += siz - idx;
	}
	for (auto edge : t[v]){
		int u = edge.first, w = edge.second;
		if (u == par or mark[u])
			continue;
		s[u] = s[v] - w + a[u];
		dp[u] = min(dp[v] - w + a[u], a[u] - w);
		pd[u] = max(pd[v], w - (a[cent] + s[v]));
		dfs(u, v);
		if (par == -1){
			dfs_add(u, v);
			sort(DP.begin(), DP.end());
			sort(PD.begin(), PD.end());
		}
	}
}

int dfs_sz(int v, int par = -1){
	sz[v] = 1;
	for (auto edge : t[v]){
		int u = edge.first;
		if (u != par and !mark[u])
			sz[v] += dfs_sz(u, v);
	}
	return sz[v];
}

void centroid_decom(int v){
	int Max = dfs_sz(v), par = -1;
	bool found = 1;
	while (found){
		found = 0;
		for (auto edge : t[v]){
			int u = edge.first;
			if (mark[u] or u == par)
				continue;
			if (sz[u] >= Max / 2){
				par = v;
				v = u;
				found = 1;
				break;
			}
		}
	}
	cent = v;
	DP.clear();
	PD.clear();
	dp[v] = 0, pd[v] = 0;
	s[v] = 0;
	DP.push_back(s[v]);
	PD.push_back(pd[v]);
	dfs(v);
	mark[v] = 1;
	for (auto edge : t[v]){
		int u = edge.first;
		if (!mark[u])
			centroid_decom(u);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 0; i < n - 1; i++){
		int v, u, w;
		cin >> v >> u >> w;
		t[v].push_back({u, w});
		t[u].push_back({v, w});
	}
	centroid_decom(1);
	cout << answer << endl;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3068 KB Output is correct
2 Correct 24 ms 3196 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3320 KB Output is correct
2 Correct 13 ms 3576 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 9464 KB Output is correct
2 Correct 71 ms 8824 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 11984 KB Output is correct
2 Correct 118 ms 13244 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 15288 KB Output is correct
2 Correct 186 ms 17764 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 5876 KB Output is correct
2 Correct 179 ms 5496 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 8204 KB Output is correct
2 Correct 122 ms 7412 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 9676 KB Output is correct
2 Correct 222 ms 9836 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 11632 KB Output is correct
2 Correct 331 ms 11828 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 14104 KB Output is correct
2 Correct 309 ms 13044 KB Output is correct