oj.uz

Submission #636743

# Submission time Handle Problem Language Result Execution time Memory
636743 2022-08-30T01:29:30 Z iee Transport (COCI19_transport) C++17
26 / 130
 1000 ms 9172 KB 
// iee
#include <bits/stdc++.h>

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define fi first
#define se second
using ll = long long;
using ull = unsigned long long;
using namespace std;
void work(int);

template <class T> void read(T &x) {
  x = 0;
  int f = 1, ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  x *= f;
}

int main() {
  int TT = 1; // cin >> TT;
  rep(CAS, 1, TT)
    work(CAS);
  return 0;
}
const int N = 1e5 + 5;
int n, a[N];
ll ans;
vector<pair<int, int>> e[N];
void dfs(int u, int pr = -1, ll W = 0) {
  if (W < 0) return;
  W += a[u], ++ans;
  for (auto ver: e[u]) {
    int v, w;
    tie(v, w) = ver;
    if (v != pr)
      dfs(v, u, W - w);
  }
}
void work(int CASE) {
  read(n);
  rep(i, 1, n) read(a[i]);
  rep(i, 1, n - 1) {
    int u, v, w;
    read(u), read(v), read(w);
    e[u].emplace_back(v, w);
    e[v].emplace_back(u, w);
  }
  rep(i, 1, n) dfs(i);
  cout << ans - n;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2772 KB Output is correct
2 Correct 9 ms 2772 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2900 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 6100 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 1094 ms 7508 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 1096 ms 9172 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 1084 ms 3668 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 1094 ms 4692 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 1084 ms 5076 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 1097 ms 5676 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 1098 ms 6868 KB Time limit exceeded
2 Halted 0 ms 0 KB -