Submission #200095

#	Time	Username	Problem	Language	Result	Execution time	Memory
200095		Saboon	Transport (COCI19_transport)	C++14	130 / 130	544 ms	17764 KiB

Main

#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 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13