oj.uz

Submission #1084572

# Submission time Handle Problem Language Result Execution time Memory
1084572 2024-09-06T12:05:08 Z avighna Firefighting (NOI20_firefighting) C++17
22 / 100
 263 ms 52672 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);
  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});
  }

  // 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 253 ms 51352 KB Output is correct
2 Correct 229 ms 51896 KB Output is correct
3 Correct 64 ms 19292 KB Output is correct
4 Correct 218 ms 49604 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 51128 KB Output is correct
2 Correct 105 ms 26624 KB Output is correct
3 Correct 105 ms 27336 KB Output is correct
4 Correct 83 ms 23756 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 192 ms 48764 KB Output is correct
8 Correct 174 ms 47360 KB Output is correct
9 Correct 172 ms 47988 KB Output is correct
10 Correct 188 ms 48060 KB Output is correct
11 Correct 236 ms 52672 KB Output is correct
12 Correct 136 ms 32396 KB Output is correct
13 Correct 64 ms 20408 KB Output is correct
14 Correct 108 ms 30660 KB Output is correct
15 Correct 139 ms 37072 KB Output is correct
16 Correct 161 ms 39624 KB Output is correct
17 Correct 144 ms 33648 KB Output is correct
18 Correct 117 ms 32964 KB Output is correct

Subtask #5
0 / 26.0

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

Subtask #6
0 / 38.0

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