oj.uz

Submission #536126

# Submission time Handle Problem Language Result Execution time Memory
536126 2022-03-12T12:10:04 Z Alex_tz307 Parkovi (COCI22_parkovi) C++17
30 / 110
 1153 ms 41848 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int kN = 2e5;
const int INF = 1e18L;
vector<pair<int, int>> g[1 + kN];
int N, depth[1 + kN], sol[kN];
bitset<1 + kN> mark, covered;

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

void minSelf(int &x, int y) {
  if (y < x) {
    x = y;
  }
}

int dfs(int u, int par, int radius) {
  if ((int)g[u].size() == 1 && par) {
    return 0;
  }
  int mx = -INF, mn = INF;
  for (auto it : g[u]) {
    int v, w;
    tie(v, w) = it;
    if (v != par) {
      int ret = dfs(v, u, radius);
      if (ret == 0 && covered[v]) { // v este acoperit si nimic din subarborele sau nu ma mai poate ajuta mai mult decat u
        maxSelf(mx, 0);
        minSelf(mn, 0);
        continue;
      }
      if (ret < 0 && ret + w <= 0) { // u este acoperit
        covered[u] = true;
      }
      if (ret < 0 && ret + w > 0) { // v sigur e acoperit si incepand de la u nu se mai acopera nimic nou, deci "resetez"
        ret = 0;
      } else { // creste distanta fata de ultimul nod marcat si mai mult
        ret += w;
      }
      if (ret > radius) { // trebuie sa il marchez pe v acum ca sa acopere alte noduri nemarcate, pentru ca deja u nu poate ajuta
        sol[N++] = v;
        mark[v] = true;
        covered[v] = true;
        ret = min(-radius + w, 0LL); // aproape analog cu cazurile anterioare
        if (w <= radius) {
          covered[u] = true;
        }
      }
      maxSelf(mx, ret);
      minSelf(mn, ret);
    }
  }
  if (mn < 0) {
    return mn;
  }
  return mx;
}

bool check(int m, int k) {
  N = 0;
  mark.reset();
  covered.reset();
  if (dfs(1, 0, m) > 0) {
    sol[N++] = 1;
    mark[1] = true;
  } else if (!covered[1]) {
    sol[N++] = 1;
    mark[1] = true;
  }
  return N <= k;
}

void testCase() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  int ans = 0, step = (1LL << 60);
  while (step) {
    if (!check(ans | step, k)) {
      ans |= step;
    }
    step /= 2;
  }
  ans += 1;
  check(ans, k);
  for (int v = 1; v <= n && N < k; ++v) {
    if (!mark[v]) {
      sol[N++] = v;
    }
  }
  cout << ans << '\n';
  for (int i = 0; i < k; ++i) {
    cout << sol[i] << ' ';
  }
  cout << '\n';
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 1; tc <= tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5028 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5028 KB Output is correct
7 Incorrect 3 ms 5076 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 34424 KB Output is correct
2 Correct 461 ms 35204 KB Output is correct
3 Correct 215 ms 19536 KB Output is correct
4 Incorrect 1153 ms 18824 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 35808 KB Output is correct
2 Correct 468 ms 39128 KB Output is correct
3 Correct 523 ms 37328 KB Output is correct
4 Correct 436 ms 37300 KB Output is correct
5 Correct 466 ms 41188 KB Output is correct
6 Correct 481 ms 40180 KB Output is correct
7 Correct 515 ms 41712 KB Output is correct
8 Correct 477 ms 39648 KB Output is correct
9 Correct 477 ms 39352 KB Output is correct
10 Correct 522 ms 38656 KB Output is correct
11 Correct 416 ms 37512 KB Output is correct
12 Correct 497 ms 41848 KB Output is correct
13 Correct 531 ms 41840 KB Output is correct
14 Correct 524 ms 40384 KB Output is correct
15 Correct 528 ms 37920 KB Output is correct
16 Correct 423 ms 36484 KB Output is correct
17 Correct 439 ms 36412 KB Output is correct
18 Correct 433 ms 38144 KB Output is correct
19 Correct 431 ms 38792 KB Output is correct
20 Correct 485 ms 39604 KB Output is correct
21 Correct 453 ms 38464 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5028 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5028 KB Output is correct
7 Incorrect 3 ms 5076 KB Output isn't correct
8 Halted 0 ms 0 KB -