oj.uz

Submission #536132

# Submission time Handle Problem Language Result Execution time Memory
536132 2022-03-12T12:33:10 Z Alex_tz307 Parkovi (COCI22_parkovi) C++17
110 / 110
 1439 ms 41844 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 (mx <= -mn) { // nodul de unde trebuie sa incep sa marchez din cauza lui mx(ca s-ar termina) va fi ori acoperit ori voi mai putea amana o eventuala marcare a sa datorita lui mn
    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5048 KB Output is correct
5 Correct 3 ms 5048 KB Output is correct
6 Correct 3 ms 5024 KB Output is correct
7 Correct 4 ms 5032 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 37216 KB Output is correct
2 Correct 494 ms 39484 KB Output is correct
3 Correct 243 ms 19076 KB Output is correct
4 Correct 1232 ms 18716 KB Output is correct
5 Correct 1213 ms 14412 KB Output is correct
6 Correct 1095 ms 14368 KB Output is correct
7 Correct 1165 ms 14448 KB Output is correct
8 Correct 1196 ms 15036 KB Output is correct
9 Correct 1172 ms 14700 KB Output is correct
10 Correct 1241 ms 14920 KB Output is correct
11 Correct 901 ms 16588 KB Output is correct
12 Correct 868 ms 16856 KB Output is correct
13 Correct 938 ms 17928 KB Output is correct
14 Correct 909 ms 16640 KB Output is correct
15 Correct 847 ms 16084 KB Output is correct
16 Correct 847 ms 16968 KB Output is correct
17 Correct 838 ms 15948 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 40140 KB Output is correct
2 Correct 488 ms 38936 KB Output is correct
3 Correct 423 ms 37324 KB Output is correct
4 Correct 447 ms 37264 KB Output is correct
5 Correct 511 ms 40960 KB Output is correct
6 Correct 510 ms 40020 KB Output is correct
7 Correct 557 ms 41560 KB Output is correct
8 Correct 505 ms 39648 KB Output is correct
9 Correct 521 ms 39356 KB Output is correct
10 Correct 557 ms 38588 KB Output is correct
11 Correct 476 ms 37404 KB Output is correct
12 Correct 502 ms 41784 KB Output is correct
13 Correct 526 ms 41844 KB Output is correct
14 Correct 528 ms 40376 KB Output is correct
15 Correct 456 ms 37908 KB Output is correct
16 Correct 435 ms 36536 KB Output is correct
17 Correct 455 ms 36416 KB Output is correct
18 Correct 499 ms 38160 KB Output is correct
19 Correct 457 ms 38720 KB Output is correct
20 Correct 473 ms 39492 KB Output is correct
21 Correct 428 ms 38460 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5048 KB Output is correct
5 Correct 3 ms 5048 KB Output is correct
6 Correct 3 ms 5024 KB Output is correct
7 Correct 4 ms 5032 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 448 ms 37216 KB Output is correct
16 Correct 494 ms 39484 KB Output is correct
17 Correct 243 ms 19076 KB Output is correct
18 Correct 1232 ms 18716 KB Output is correct
19 Correct 1213 ms 14412 KB Output is correct
20 Correct 1095 ms 14368 KB Output is correct
21 Correct 1165 ms 14448 KB Output is correct
22 Correct 1196 ms 15036 KB Output is correct
23 Correct 1172 ms 14700 KB Output is correct
24 Correct 1241 ms 14920 KB Output is correct
25 Correct 901 ms 16588 KB Output is correct
26 Correct 868 ms 16856 KB Output is correct
27 Correct 938 ms 17928 KB Output is correct
28 Correct 909 ms 16640 KB Output is correct
29 Correct 847 ms 16084 KB Output is correct
30 Correct 847 ms 16968 KB Output is correct
31 Correct 838 ms 15948 KB Output is correct
32 Correct 503 ms 40140 KB Output is correct
33 Correct 488 ms 38936 KB Output is correct
34 Correct 423 ms 37324 KB Output is correct
35 Correct 447 ms 37264 KB Output is correct
36 Correct 511 ms 40960 KB Output is correct
37 Correct 510 ms 40020 KB Output is correct
38 Correct 557 ms 41560 KB Output is correct
39 Correct 505 ms 39648 KB Output is correct
40 Correct 521 ms 39356 KB Output is correct
41 Correct 557 ms 38588 KB Output is correct
42 Correct 476 ms 37404 KB Output is correct
43 Correct 502 ms 41784 KB Output is correct
44 Correct 526 ms 41844 KB Output is correct
45 Correct 528 ms 40376 KB Output is correct
46 Correct 456 ms 37908 KB Output is correct
47 Correct 435 ms 36536 KB Output is correct
48 Correct 455 ms 36416 KB Output is correct
49 Correct 499 ms 38160 KB Output is correct
50 Correct 457 ms 38720 KB Output is correct
51 Correct 473 ms 39492 KB Output is correct
52 Correct 428 ms 38460 KB Output is correct
53 Correct 1149 ms 14588 KB Output is correct
54 Correct 1208 ms 14876 KB Output is correct
55 Correct 1367 ms 15292 KB Output is correct
56 Correct 1314 ms 15136 KB Output is correct
57 Correct 1349 ms 16152 KB Output is correct
58 Correct 1202 ms 14780 KB Output is correct
59 Correct 1428 ms 17720 KB Output is correct
60 Correct 1357 ms 15312 KB Output is correct
61 Correct 1085 ms 14356 KB Output is correct
62 Correct 1178 ms 15832 KB Output is correct
63 Correct 1337 ms 15308 KB Output is correct
64 Correct 1319 ms 17216 KB Output is correct
65 Correct 1220 ms 15000 KB Output is correct
66 Correct 1295 ms 15852 KB Output is correct
67 Correct 1185 ms 14416 KB Output is correct
68 Correct 1439 ms 17792 KB Output is correct
69 Correct 494 ms 35128 KB Output is correct
70 Correct 436 ms 33612 KB Output is correct
71 Correct 524 ms 37284 KB Output is correct
72 Correct 194 ms 14512 KB Output is correct
73 Correct 219 ms 14664 KB Output is correct
74 Correct 279 ms 15920 KB Output is correct
75 Correct 837 ms 17184 KB Output is correct
76 Correct 990 ms 17684 KB Output is correct
77 Correct 842 ms 17008 KB Output is correct
78 Correct 889 ms 17792 KB Output is correct