Submission #1084397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084397		avighna	Firefighting (NOI20_firefighting)	C++17	17 / 100	3057 ms	27948 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);
  ll min_w = 1e15;
  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});
    min_w = std::min(min_w, w);
  }

  if (k < min_w) {
    std::cout << n << '\n';
    for (ll i = 1; i <= n; ++i) {
      std::cout << i << ' ';
    }
    std::cout << '\n';
    return 0;
  }

  std::pair<ll, ll> ans = {1e15, -1};
  for (ll mask = 1; mask < (1 << n); ++mask) {
    std::priority_queue<std::pair<ll, ll>> pq;
    std::vector<bool> vis(n + 1);
    std::vector<ll> dist(n + 1, 1e15);
    dist[0] = 0;
    for (ll i = 0; i < n; ++i) {
      if (mask & (1 << i)) {
        dist[i + 1] = 0;
        pq.push({0, i + 1});
      }
    }
    while (!pq.empty()) {
      auto [d, node] = pq.top();
      pq.pop();
      if (vis[node]) {
        continue;
      }
      vis[node] = true;
      d *= -1;
      for (auto &[ch, w] : adj[node]) {
        if (d + w < dist[ch]) {
          dist[ch] = d + w;
          pq.push({-dist[ch], ch});
        }
      }
    }
    if (*std::max_element(dist.begin(), dist.end()) <= k) {
      ans = std::min(ans, {__builtin_popcount(mask), mask});
    }
  }
  std::cout << ans.first << '\n';
  for (ll i = 0; i < n; ++i) {
    if (ans.second & (1 << i)) {
      std::cout << i + 1 << ' ';
    }
  }
  std::cout << '\n';
}

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