Submission #264868

#	Time	Username	Problem	Language	Result	Execution time	Memory
264868		NONAME	Transport (COCI19_transport)	C++14	26 / 130	1093 ms	15608 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5 + 500;

int n;
ll a[N];
vector <pair <int, ll> > g[N];

ll dfs(int v, int pr, ll d) {
	if (d < 0)
		return 0;
              
	ll res = (pr != -1);                  
	for (auto to : g[v]) {
	 	if (to.first == pr)
	 		continue;

		res += dfs(to.first, v, d + a[v] - to.second);
	}
                                         
	return res;
}               

int main() {          
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie();

	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];

	for (int i = 0; i < n - 1; ++i) {
	 	int x, y, z;
	 	cin >> x >> y >> z;
	 	--x, --y;

	 	g[x].push_back(make_pair(y, z));
	 	g[y].push_back(make_pair(x, z));
	}

	ll ans = 0;
	for (int i = 0; i < n; ++i)
		ans += dfs(i, -1, 0);

	cout << ans << "\n";
}

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13