oj.uz

Submission #494102

# Submission time Handle Problem Language Result Execution time Memory
494102 2021-12-14T10:51:27 Z peijar Road Closures (APIO21_roads) C++17
0 / 100
 2000 ms 11460 KB 
#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;
const int MAXN = 1e5;

vector<pair<int, int>> adj[MAXN];
bool seen[MAXN];

// [withPar, withoutPar]
pair<int, int> dfs(int u, int p, int maxDeg) {
  assert(!seen[u]);
  seen[u] = true;
  int coutInit = 0;
  vector<int> swaps;
  for (auto [v, w] : adj[u])
    if (v != p) {

      if ((int)adj[v].size() <= maxDeg) {
        swaps.push_back(w);
        continue;
      }

      auto [withPar, withoutPar] = dfs(v, u, maxDeg);

      coutInit += withPar;
      assert(coutInit < INF);
      swaps.push_back(withoutPar + w - withPar);
    }

  sort(swaps.begin(), swaps.end());

  // withPar :
  int toRem = adj[u].size() - maxDeg;
  int withPar = INF;
  if (toRem <= 0)
    withPar = coutInit;
  int accu = coutInit;

  for (int i = 0; i < (int)swaps.size(); ++i) {
    accu += swaps[i];
    if (i + 1 >= toRem)
      withPar = min(withPar, accu);
  }

  // withoutPar
  toRem = adj[u].size() - maxDeg - (u != p);
  int withoutPar = INF;
  if (toRem <= 0)
    withoutPar = coutInit;
  accu = coutInit;
  for (int i = 0; i < (int)swaps.size(); ++i) {
    accu += swaps[i];
    if (i + 1 >= toRem)
      withoutPar = min(withoutPar, accu);
  }
  return pair(withPar, withoutPar);
}

vector<int> minimum_closure_costs(signed N, vector<signed> U, vector<signed> V,
                                  vector<signed> W) {

  for (int i = 0; i < N - 1; ++i) {
    adj[U[i]].emplace_back(V[i], W[i]);
    adj[V[i]].emplace_back(U[i], W[i]);
  }

  vector<int> order(N);
  iota(order.begin(), order.end(), 0LL);
  sort(order.begin(), order.end(),
       [&](int i, int j) { return adj[i].size() > adj[j].size(); });

  vector<int> ret(N);
  ret[0] = accumulate(W.begin(), W.end(), 0LL);

  for (int k = 1; k < N; ++k) {
    for (int i = 0; i < N and (int) adj[i].size() > k; ++i)
      if (!seen[i])
        ret[k] += dfs(i, i, k).first;
    for (int i = 0; i < N and (int) adj[i].size() > k; ++i)
      seen[i] = false;
  }

  // for (int k = 1; k < N; ++k)
  // ret[k] = dfs(0, 0, k).first;
  return ret;

  if (U == vector<signed>(N - 1, 0)) {
    vector<int> prefSum(N);
    sort(W.begin(), W.end());
    for (int i = 0; i < N - 1; ++i)
      prefSum[i + 1] = prefSum[i] + W[i];
    reverse(prefSum.begin(), prefSum.end());

    return prefSum;
  }
  return vector<int>(N, 0);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 132 ms 2820 KB Output is correct
3 Correct 155 ms 2832 KB Output is correct
4 Correct 52 ms 2844 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 69 ms 2824 KB Output is correct
9 Correct 87 ms 2836 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Execution timed out 2093 ms 9000 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Runtime error 4 ms 5196 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Runtime error 4 ms 5196 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 11460 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 2636 KB Output is correct
2 Correct 132 ms 2820 KB Output is correct
3 Correct 155 ms 2832 KB Output is correct
4 Correct 52 ms 2844 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 69 ms 2824 KB Output is correct
9 Correct 87 ms 2836 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Execution timed out 2093 ms 9000 KB Time limit exceeded
13 Halted 0 ms 0 KB -