oj.uz

Submission #494105

# Submission time Handle Problem Language Result Execution time Memory
494105 2021-12-14T11:07:46 Z peijar Road Closures (APIO21_roads) C++17
0 / 100
 2000 ms 22620 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];
vector<int> prefSum[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;

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

  // withoutPar
  toRem = adj[u].size() - maxDeg - (u != p);
  int withoutPar = INF;
  if (toRem <= 0)
    withoutPar = coutInit;
  accu = coutInit;
  if (toRem > 0)
    for (int i = 0; i < (int)swaps.size(); ++i) {
      accu += swaps[i];
      if (i + 1 >= toRem) {
        withoutPar = min(withoutPar, accu);
        // break;
      }
    }
  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(); });

  for (int i = 0; i < N; ++i) {
    sort(adj[i].begin(), adj[i].end(), [&](auto u, auto v) {
      return adj[u.first].size() < adj[v.first].size();
    });
    prefSum[i].resize(adj[i].size() + 1);
    for (int j = 0; j < (int)adj[i].size(); ++j)
      prefSum[i][j + 1] = prefSum[i][j] + adj[i][j].second;
  }

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

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

  return ret;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 152 ms 5352 KB Output is correct
3 Correct 164 ms 5264 KB Output is correct
4 Correct 57 ms 5252 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 62 ms 5224 KB Output is correct
9 Correct 88 ms 5256 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Execution timed out 2083 ms 13664 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 4940 KB Output is correct
2 Incorrect 59 ms 22620 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 17292 KB Output is correct
2 Correct 105 ms 17136 KB Output is correct
3 Correct 570 ms 18584 KB Output is correct
4 Correct 114 ms 17688 KB Output is correct
5 Correct 546 ms 18692 KB Output is correct
6 Execution timed out 2083 ms 17604 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 17292 KB Output is correct
2 Correct 105 ms 17136 KB Output is correct
3 Correct 570 ms 18584 KB Output is correct
4 Correct 114 ms 17688 KB Output is correct
5 Correct 546 ms 18692 KB Output is correct
6 Execution timed out 2083 ms 17604 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 152 ms 5352 KB Output is correct
3 Correct 164 ms 5264 KB Output is correct
4 Correct 57 ms 5252 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 62 ms 5224 KB Output is correct
9 Correct 88 ms 5256 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Execution timed out 2083 ms 13664 KB Time limit exceeded
13 Halted 0 ms 0 KB -