제출 #1196677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196677		mmaiti	Petrol stations (CEOI24_stations)	C++20	18 / 100	3594 ms	12480 KiB

Main

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vi vector<int>
#define si set<int>
#define usi unordered_set<int>
#define sll set<ll>
#define usll unordered_set<ll>
#define vb vector<bool>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>

ll N, K;
vector<vector<pll>> AL;
vll stops;
vll stsz;

ll fillSz(int num, int par) {
  stsz[num] = 1;
  for (auto i : AL[num]) {
    auto [nx, cost] = i;
    if (nx == par)
      continue;
    stsz[num] += fillSz(nx, num);
  }
  return stsz[num];
}
void dfs(int num, int par, int fuel) {
  for (auto i : AL[num]) {
    auto [nx, cost] = i;
    if (nx == par)
      continue;
    if (fuel - cost < 0) {
      stops[num] += stsz[nx];
      dfs(nx, num, K - cost);
    } else {
      dfs(nx, num, fuel - cost);
    }
  }
}
void solve() {
  cin >> N >> K;
  AL.resize(N);
  stops.resize(N);
  stsz.resize(N);
  ll a, b, w;
  for (int i = 0; i < N - 1; i++) {
    cin >> a >> b >> w;
    AL[a].push_back({b, w});
    AL[b].push_back({a, w});
  }
  for (int i = 0; i < N; i++) {
    fillSz(i, -1);
    dfs(i, -1, K);
  }
  for (int i = 0; i < N; i++)
    cout << stops[i] << "\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  solve();
}

• Subtask 0: 0 / 0
• Subtask 1: 18 / 18
• Subtask 2: 0 / 8
• Subtask 3: 0 / 10
• Subtask 4: 0 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35