제출 #1339512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1339512		Ianis	Transport (COCI19_transport)	C++17	0 / 100	0 ms	0 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int NMAX = 1e5+5;

struct Edge {
   int y, w;
};

int n, m;
int a[NMAX];
vector<Edge> g[NMAX];
ll ans;

void read() {
   cin >> n;
   for (int i = 1; i <= n; i++) {
      cin >> a[i];
   }
   for (int i = 1, x, y, w; i < n; i++) {
      cin >> x >> y >> w;
      g[x].push_back({ y, w });
      g[y].push_back({ x, w });
   }
}

void dfs(int x, int daddy = 0, int sum = 0) {
   ans += daddy != 0;
   sum += a[x];
   for (auto [ y, w ] : g[x]) {
      if (y != daddy && sum >= w) {
         dfs(y, x, sum - w);
      }
   }
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#endif

   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

   read();
   for (int i = 1; i <= n; i++) {
      dfs(i);
   }
   cout << ans << '\n';

   return 0;
}

• Subtask 1: 0 / 100