Submission #1084719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084719		avighna	Firefighting (NOI20_firefighting)	C++17	100 / 100	212 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;
    ll 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) {
      // We cover everything in the subtree
      ret = {true, station_reachability - parent_edge};
    } else {
      // Okay, let's update the furthest node
      ret = {false, furthest_unprotected + parent_edge};
    }

    if (!ret.first and ret.second > k) {
      // If x => par[x] makes a node unreachable from anything outside x's
      // subtree, then x is a forced pick.
      ans.push_back(x);
      ret = {true, k - parent_edge};
    }

    // If this happens, we aren't protecting anything anymore. At the same time,
    // we have still protected everything in our subtree.
    if (ret.first and ret.second < 0) {
      ret = {false, 0};
    }
    return ret;
  };
  // The reason we're making the parent edge very large is because by default
  // our algorithm tries to get the parent to place down a fire station if the
  // distance is small enough, since this is optimal. However, in the case of 1,
  // we have no parent, so this would behave as if there was a large barrier
  // between 1 and its parent, forcing a placemenet (if necessary) at 1 itself.
  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