oj.uz

Submission #1084574

# Submission time Handle Problem Language Result Execution time Memory
1084574 2024-09-06T12:07:57 Z avighna Firefighting (NOI20_firefighting) C++17
36 / 100
 217 ms 42940 KB 
#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;
  }

  if (n <= 17) {
    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';
    return 0;
  }

  // dp[node][0] => you need to cover parent
  // dp[node][1] => parent covers you
  // dp[node][2] => you only need to cover your subtree
  std::vector<std::vector<ll>> dp(n + 1, std::vector<ll>(3, 1e15));
  std::vector<bool> is_leaf(n + 1, true);
  std::function<void(ll, ll, ll)> dfs;
  dfs = [&](ll node, ll par, ll wt) {
    ll sum = 0;
    for (auto &[ch, w] : adj[node]) {
      if (ch == par) {
        continue;
      }
      is_leaf[node] = false;
      dfs(ch, node, w);
      sum += dp[ch][2];
    }
    if (is_leaf[node]) {
      dp[node][0] = wt <= k ? 1 : 1e15;
      dp[node][1] = wt <= k ? 0 : 1e15;
      dp[node][2] = 1;
    } else {
      dp[node][0] = 1;
      dp[node][1] = 0;
      for (auto &[ch, w] : adj[node]) {
        if (ch == par) {
          continue;
        }
        if (w <= k) {
          dp[node][2] = std::min(dp[node][2], sum - dp[ch][2] + dp[ch][0]);
          dp[node][0] += dp[ch][1];
        } else {
          dp[node][0] += dp[ch][2];
        }
        dp[node][1] += dp[ch][2];
      }
      dp[node][1] = std::min(dp[node][1], dp[node][0]);
      dp[node][2] = std::min(dp[node][2], dp[node][0]);
    }
  };
  dfs(1, 0, 0);

  std::vector<ll> ans;
  std::function<void(ll, ll, ll)> build_ans;
  build_ans = [&](ll node, ll par, ll j) {
    if (is_leaf[node]) {
      if (j == 0 or j == 2) {
        ans.push_back(node);
      }
      return;
    }
    if (j == 0) {
      ans.push_back(node);
      for (auto &[ch, w] : adj[node]) {
        if (ch == par) {
          continue;
        }
        if (w <= k) {
          build_ans(ch, node, 1);
        } else {
          build_ans(ch, node, 2);
        }
      }
    } else if (j == 1) {
      if (dp[node][1] == dp[node][0]) {
        build_ans(node, par, 0);
        return;
      }
      for (auto &[ch, w] : adj[node]) {
        if (ch == par) {
          continue;
        }
        build_ans(ch, node, 2);
      }
    } else {
      if (dp[node][2] == dp[node][0]) {
        build_ans(node, par, 0);
        return;
      }
      ll sum = 0;
      for (auto &[ch, w] : adj[node]) {
        if (ch == par) {
          continue;
        }
        sum += dp[ch][2];
      }
      bool found = false;
      for (auto &[ch, w] : adj[node]) {
        if (ch == par) {
          continue;
        }
        if (!found and dp[node][2] == sum - dp[ch][2] + dp[ch][0]) {
          found = true;
          build_ans(ch, node, 0);
        } else {
          build_ans(ch, node, 2);
        }
      }
    }
  };
  build_ans(1, 0, 2);
  std::cout << dp[1][2] << '\n';
  for (auto &i : ans) {
    std::cout << i << ' ';
  }
  std::cout << '\n';
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 25172 KB Output is correct
2 Correct 122 ms 25216 KB Output is correct
3 Correct 37 ms 9548 KB Output is correct
4 Correct 106 ms 24644 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 32 ms 344 KB Output is correct
6 Correct 35 ms 348 KB Output is correct
7 Correct 81 ms 348 KB Output is correct
8 Correct 74 ms 344 KB Output is correct
9 Correct 72 ms 344 KB Output is correct
10 Correct 75 ms 348 KB Output is correct
11 Correct 73 ms 440 KB Output is correct
12 Correct 81 ms 348 KB Output is correct
13 Correct 75 ms 432 KB Output is correct
14 Correct 4 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 436 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 76 ms 348 KB Output is correct
4 Correct 37 ms 428 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 75 ms 348 KB Output is correct
10 Correct 86 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 84 ms 432 KB Output is correct
13 Correct 38 ms 348 KB Output is correct
14 Correct 41 ms 348 KB Output is correct
15 Correct 92 ms 436 KB Output is correct
16 Correct 45 ms 348 KB Output is correct
17 Correct 96 ms 436 KB Output is correct
18 Correct 43 ms 428 KB Output is correct
19 Correct 82 ms 436 KB Output is correct
20 Correct 91 ms 344 KB Output is correct
21 Correct 94 ms 440 KB Output is correct
22 Correct 84 ms 348 KB Output is correct
23 Correct 87 ms 344 KB Output is correct
24 Correct 85 ms 344 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 86 ms 440 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 25192 KB Output is correct
2 Correct 89 ms 24012 KB Output is correct
3 Correct 89 ms 24648 KB Output is correct
4 Correct 80 ms 21452 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 176 ms 42644 KB Output is correct
8 Correct 179 ms 42684 KB Output is correct
9 Correct 188 ms 42680 KB Output is correct
10 Correct 175 ms 42940 KB Output is correct
11 Correct 114 ms 25172 KB Output is correct
12 Correct 141 ms 29384 KB Output is correct
13 Correct 67 ms 18388 KB Output is correct
14 Correct 113 ms 27592 KB Output is correct
15 Correct 158 ms 33488 KB Output is correct
16 Correct 175 ms 35780 KB Output is correct
17 Correct 145 ms 30412 KB Output is correct
18 Correct 153 ms 29636 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 39776 KB Output isn't correct
2 Halted 0 ms 0 KB -