Submission #1084721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084721		avighna	Firefighting (NOI20_firefighting)	C++17	100 / 100	215 ms	51652 KiB

Firefighting

#include <bits/stdc++.h>

typedef long long ll;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, k;
  std::cin >> n >> k;
  std::vector<std::vector<std::pair<ll, ll>>> adj(n + 1);
  for (ll i = 0, u, v, w; i < n - 1; ++i) {
    std::cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }

  std::vector<ll> ans;
  std::function<std::pair<bool, ll>(ll, ll, ll)> dfs;
  dfs = [&](ll x, ll par, ll parent_edge) {
    ll furthest_unprotected = 0, station_reachability = -1e15;
    for (auto &[to, w] : adj[x]) {
      if (to == par) {
        continue;
      }
      auto res = dfs(to, x, w);
      if (res.first) {
        station_reachability = std::max(station_reachability, res.second);
      } else {
        furthest_unprotected = std::max(furthest_unprotected, res.second);
      }
    }
    std::pair<bool, ll> ret;
    if (station_reachability >= furthest_unprotected) {
      ret = {true, station_reachability - parent_edge};
    } else {
      ret = {false, furthest_unprotected + parent_edge};
    }
    if (!ret.first and ret.second > k) {
      ans.push_back(x);
      ret = {true, k - parent_edge};
    }
    if (ret.first and ret.second < 0) {
      ret = {false, 0};
    }
    return ret;
  };
  dfs(1, 0, 1e15);

  std::cout << ans.size() << '\n';
  for (auto &i : ans) {
    std::cout << i << ' ';
  }
  std::cout << '\n';
}

• Subtask 1: 3 / 3
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26
• Subtask 6: 38 / 38