oj.uz

Submission #264868

# Submission time Handle Problem Language Result Execution time Memory
264868 2020-08-14T10:42:10 Z NONAME Transport (COCI19_transport) C++14
26 / 130
 1000 ms 15608 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2944 KB Output is correct
2 Correct 15 ms 3200 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3328 KB Output is correct
2 Correct 5 ms 3072 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 9592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 12280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 15608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 5112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 6520 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 7928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 9464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 11896 KB Time limit exceeded
2 Halted 0 ms 0 KB -