oj.uz

Submission #717971

# Submission time Handle Problem Language Result Execution time Memory
717971 2023-04-03T00:57:20 Z khulegub Race (IOI11_race) C++14
100 / 100
 1224 ms 45772 KB 
// Author: Khulegu Batnasan
// Date: 2023-04-03

#include "race.h"
#include<bits/stdc++.h>

const int MAXN = 1000005;
const int INF = 1000010;
using namespace std;

vector<vector<pair<int, int>>> to;
int n, k;
int ans = INF;
int sz[MAXN];
bool del[MAXN];
// Backlog
map<int, int> dist_min_back;
// <K, V> Save the minimum number of edges with K total length
map<int, int> dist_min;

void calc_size(int u, int pre) {
  sz[u] = 1;
  for (auto [v, w] : to[u]) {
    if (v == pre || del[v]) continue;
    calc_size(v, u);
    sz[u] += sz[v];
  }
}

int find_centroid(int u, int pre, int total) {
  for (auto [v, w] : to[u]) {
    if (v == pre || del[v]) continue;
    if (sz[v] > total / 2) return find_centroid(v, u, total);
  }
  return u;
}

void collect_distances(int u, int pre, int dist, int edges) {
  if (dist_min.count(dist)) {
    dist_min[dist] = min(dist_min[dist], edges);
  } else {
    dist_min[dist] = edges;
  }

  for (auto [v, w] : to[u]) {
    if (v == pre || del[v]) continue;
    collect_distances(v, u, dist + w, edges + 1);
  }
}

void solve_subtree(int u) {
  // Recalculate subtree sizes
  calc_size(u, u);

  // Find the centroid
  int centroid = find_centroid(u, u, sz[u]);

  // Mark the centroid as deleted
  del[centroid] = true;

  dist_min_back.clear();
  dist_min_back[0] = 0;
  
  // Decompose
  for (auto [v, w] : to[centroid]) {
    if (del[v]) continue;
    
    dist_min.clear();

    collect_distances(v, centroid, w, 1);

    // Calculate the answers with backlog
    for (auto [dist, edges] : dist_min) {
      if (dist_min_back.count(k - dist)) {
        int new_ans = dist_min_back[k - dist] + edges;
        ans = min(ans, new_ans);
      }
    }

    // Add to backlog
    for (auto [dist, edges] : dist_min) {
      if (dist_min_back.count(dist)) {
        dist_min_back[dist] = min(dist_min_back[dist], edges);
      } else {
        dist_min_back[dist] = edges;
      }
    }
  }

  // Solve the subtrees
  for (auto [v, w] : to[centroid]) {
    if (del[v]) continue;
    solve_subtree(v);
  }
}

int best_path(int _n, int _k, int H[][2], int L[]) {
  // Given a tree with N vertices with
  // edges H[i][0] and H[i][1] connected
  // And edge lengths L[i].
  // Find a minimum number of edges with
  // their total length equal to exactly K.
  // If no such path exists, return -1.

  n = _n, k = _k;

  to.resize(n);

  for (int i = 0; i < n - 1; i++) {
    int u = H[i][0], v = H[i][1], w = L[i];
    to[u].push_back({v, w});
    to[v].push_back({u, w});
  }

  solve_subtree(0);

  return ans == INF ? -1 : ans;
}

Compilation message

race.cpp: In function 'void calc_size(int, int)':
race.cpp:23:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |   for (auto [v, w] : to[u]) {
      |             ^
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:31:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |   for (auto [v, w] : to[u]) {
      |             ^
race.cpp: In function 'void collect_distances(int, int, int, int)':
race.cpp:45:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |   for (auto [v, w] : to[u]) {
      |             ^
race.cpp: In function 'void solve_subtree(int)':
race.cpp:65:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |   for (auto [v, w] : to[centroid]) {
      |             ^
race.cpp:73:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for (auto [dist, edges] : dist_min) {
      |               ^
race.cpp:81:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |     for (auto [dist, edges] : dist_min) {
      |               ^
race.cpp:91:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |   for (auto [v, w] : to[centroid]) {
      |             ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 3 ms 468 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 3 ms 468 KB Output is correct
33 Correct 3 ms 456 KB Output is correct
34 Correct 3 ms 468 KB Output is correct
35 Correct 3 ms 468 KB Output is correct
36 Correct 3 ms 468 KB Output is correct
37 Correct 2 ms 468 KB Output is correct
38 Correct 3 ms 468 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 234 ms 9020 KB Output is correct
20 Correct 231 ms 9268 KB Output is correct
21 Correct 216 ms 9360 KB Output is correct
22 Correct 202 ms 9472 KB Output is correct
23 Correct 349 ms 9704 KB Output is correct
24 Correct 167 ms 9536 KB Output is correct
25 Correct 176 ms 13340 KB Output is correct
26 Correct 87 ms 16576 KB Output is correct
27 Correct 352 ms 17776 KB Output is correct
28 Correct 1186 ms 45772 KB Output is correct
29 Correct 1224 ms 44544 KB Output is correct
30 Correct 354 ms 17672 KB Output is correct
31 Correct 357 ms 17636 KB Output is correct
32 Correct 404 ms 17612 KB Output is correct
33 Correct 605 ms 16588 KB Output is correct
34 Correct 1059 ms 28096 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 3 ms 468 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 3 ms 468 KB Output is correct
33 Correct 3 ms 456 KB Output is correct
34 Correct 3 ms 468 KB Output is correct
35 Correct 3 ms 468 KB Output is correct
36 Correct 3 ms 468 KB Output is correct
37 Correct 2 ms 468 KB Output is correct
38 Correct 3 ms 468 KB Output is correct
39 Correct 234 ms 9020 KB Output is correct
40 Correct 231 ms 9268 KB Output is correct
41 Correct 216 ms 9360 KB Output is correct
42 Correct 202 ms 9472 KB Output is correct
43 Correct 349 ms 9704 KB Output is correct
44 Correct 167 ms 9536 KB Output is correct
45 Correct 176 ms 13340 KB Output is correct
46 Correct 87 ms 16576 KB Output is correct
47 Correct 352 ms 17776 KB Output is correct
48 Correct 1186 ms 45772 KB Output is correct
49 Correct 1224 ms 44544 KB Output is correct
50 Correct 354 ms 17672 KB Output is correct
51 Correct 357 ms 17636 KB Output is correct
52 Correct 404 ms 17612 KB Output is correct
53 Correct 605 ms 16588 KB Output is correct
54 Correct 1059 ms 28096 KB Output is correct
55 Correct 26 ms 1612 KB Output is correct
56 Correct 14 ms 1228 KB Output is correct
57 Correct 140 ms 9520 KB Output is correct
58 Correct 53 ms 9224 KB Output is correct
59 Correct 439 ms 22556 KB Output is correct
60 Correct 1210 ms 44316 KB Output is correct
61 Correct 442 ms 18880 KB Output is correct
62 Correct 360 ms 17612 KB Output is correct
63 Correct 413 ms 17640 KB Output is correct
64 Correct 1127 ms 23904 KB Output is correct
65 Correct 1024 ms 27132 KB Output is correct
66 Correct 1207 ms 42132 KB Output is correct
67 Correct 132 ms 17840 KB Output is correct
68 Correct 552 ms 25652 KB Output is correct
69 Correct 566 ms 25836 KB Output is correct
70 Correct 508 ms 24536 KB Output is correct