oj.uz

Submission #682551

# Submission time Handle Problem Language Result Execution time Memory
682551 2023-01-16T13:38:11 Z vjudge1 Parkovi (COCI22_parkovi) C++17
30 / 110
 1016 ms 41884 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 2 ms 5076 KB Output is correct
2 Correct 3 ms 5036 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5032 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Incorrect 3 ms 5032 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 37352 KB Output is correct
2 Correct 470 ms 39492 KB Output is correct
3 Correct 209 ms 19580 KB Output is correct
4 Incorrect 1016 ms 18832 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 484 ms 40116 KB Output is correct
2 Correct 455 ms 39168 KB Output is correct
3 Correct 430 ms 37380 KB Output is correct
4 Correct 424 ms 37304 KB Output is correct
5 Correct 472 ms 41096 KB Output is correct
6 Correct 481 ms 40260 KB Output is correct
7 Correct 489 ms 41820 KB Output is correct
8 Correct 464 ms 39660 KB Output is correct
9 Correct 460 ms 39380 KB Output is correct
10 Correct 444 ms 38704 KB Output is correct
11 Correct 433 ms 37412 KB Output is correct
12 Correct 593 ms 41884 KB Output is correct
13 Correct 502 ms 41860 KB Output is correct
14 Correct 545 ms 40392 KB Output is correct
15 Correct 461 ms 37964 KB Output is correct
16 Correct 414 ms 36540 KB Output is correct
17 Correct 443 ms 36424 KB Output is correct
18 Correct 448 ms 38172 KB Output is correct
19 Correct 462 ms 38836 KB Output is correct
20 Correct 441 ms 39580 KB Output is correct
21 Correct 449 ms 38484 KB Output is correct

Subtask #4
0 / 60.0

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