oj.uz

Submission #964681

# Submission time Handle Problem Language Result Execution time Memory
964681 2024-04-17T10:25:41 Z kilkuwu Road Closures (APIO21_roads) C++17
7 / 100
 62 ms 27696 KB 
#include "roads.h"

#include <bits/stdc++.h>

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {

  std::vector<long long> res(N);

  std::vector<std::vector<std::pair<int, int>>> adj(N);
  long long tot = 0;
  for (int i = 0; i + 1 < N; i++) {
    int u = U[i], v = V[i], w = W[i];
    adj[u].emplace_back(w, v);
    adj[v].emplace_back(w, u);
    tot += w;
  }

  std::vector<std::array<long long, 2>> dp(N, {-1, -1});
  res[0] = tot;
  auto dfs = [&](auto self, int u, int p, bool state) -> long long { // state is for Jj
    if (dp[u][state] != -1) return dp[u][state];
    int child = 0;
    long long ans = 1e18;
    for (auto [w, v] : adj[u]) {
      if (v == p) continue;
      child++;
      // now we check it 
      if (state) {
        ans = std::min(ans, w + self(self, v, u, 0)); 
      } else {
        // we can either delete or not 
        auto cand = self(self, v, u, 1);
        auto cand2 = w + self(self, v, u, 0); // disconnect it 
        cand = std::min(cand, cand2);
        ans = std::min(ans, cand);
      }
    }

    if (child == 0) {
      return dp[u][state] = 0;
    } else {
      return dp[u][state] = ans;
    }
  };

  res[1] = dfs(dfs, 0, -1, 0);
  return res;
}

Subtask #1
0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 47 ms 22016 KB Output is correct
3 Correct 48 ms 25668 KB Output is correct
4 Correct 52 ms 27496 KB Output is correct
5 Correct 51 ms 27696 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 29 ms 16116 KB Output is correct
13 Correct 50 ms 26708 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 50 ms 24116 KB Output is correct
16 Correct 60 ms 26844 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 25.0

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

Subtask #7
0 / 22.0

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