oj.uz

Submission #536127

# Submission time Handle Problem Language Result Execution time Memory
536127 2022-03-12T12:10:58 Z Alex_tz307 Parkovi (COCI22_parkovi) C++17
30 / 110
 1170 ms 38116 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 5076 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Incorrect 3 ms 4948 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 34472 KB Output is correct
2 Correct 471 ms 35372 KB Output is correct
3 Correct 265 ms 15048 KB Output is correct
4 Incorrect 1170 ms 14708 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 470 ms 35816 KB Output is correct
2 Correct 468 ms 34964 KB Output is correct
3 Correct 414 ms 33356 KB Output is correct
4 Correct 456 ms 33292 KB Output is correct
5 Correct 538 ms 36948 KB Output is correct
6 Correct 482 ms 36016 KB Output is correct
7 Correct 480 ms 37404 KB Output is correct
8 Correct 465 ms 35916 KB Output is correct
9 Correct 561 ms 35664 KB Output is correct
10 Correct 438 ms 34952 KB Output is correct
11 Correct 431 ms 33996 KB Output is correct
12 Correct 507 ms 38088 KB Output is correct
13 Correct 495 ms 38116 KB Output is correct
14 Correct 484 ms 36816 KB Output is correct
15 Correct 466 ms 35028 KB Output is correct
16 Correct 435 ms 33784 KB Output is correct
17 Correct 417 ms 33784 KB Output is correct
18 Correct 426 ms 35136 KB Output is correct
19 Correct 430 ms 36064 KB Output is correct
20 Correct 533 ms 36652 KB Output is correct
21 Correct 430 ms 35676 KB Output is correct

Subtask #4
0 / 60.0

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