oj.uz

Submission #1108829

# Submission time Handle Problem Language Result Execution time Memory
1108829 2024-11-05T09:45:53 Z eym Race (IOI11_race) C++17
21 / 100
 3000 ms 12496 KB 
#include "race.h"

#include <sys/resource.h>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

using i6 = int64_t;

struct Edge {
  int len;
  int dst;
};

vector<vector<Edge>> g;

int res = INT32_MAX;
int n;
int k;

vector<uint8_t> used;

int find_centroid(int root, int total_size) {
  vector<int> sizes(n, 1);
  function<void(int, int)> find_sizes = [&](int p, int u) -> void {
    for (auto e : g[u]) {
      if (e.dst == p || used[e.dst])
        continue;
      find_sizes(u, e.dst);
      sizes.at(u) += sizes.at(e.dst);
    }
    // cout << u << " has size " << sizes[u] << " in " << root << " (in `find_sizes`)" << endl;
  };
  find_sizes(-1, root);

  function<int(int, int)> find_centroid_impl = [&](int p, int u) {
    for (auto e : g[u]) {
      if (e.dst == p || used[e.dst])
        continue;
      // cout << e.dst << " has size " << sizes.at(e.dst) << " in " << root << endl;
      if (sizes[e.dst] > total_size / 2) {
        return find_centroid_impl(u, e.dst);
      }
    }
    return u;
  };
  auto centroid = find_centroid_impl(-1, root);
  // cout << "the subtree of " << root << " has " << total_size << " vertices to process and
  // centroid "
  //      << centroid << endl;
  return centroid;
}

void compute_solution(int root, int total_size) {
  if (used[root])
    return;

  int centroid = find_centroid(root, total_size);
  used[centroid] = 1;

  unordered_map<int, int> comp_sizes;

  {
    unordered_map<i6, int> min_depth_by_dist;
    unordered_map<i6, int> new_min_depth_by_dist;

    int comp_size = 0;
    function<void(int, int, int, i6)> walk = [&](int parent, int u, int depth, i6 dist) {
      comp_size++;
      if (dist <= k && depth < res) {  // heuristic
        auto it = new_min_depth_by_dist.find(dist);
        if (it == new_min_depth_by_dist.end()) {
          new_min_depth_by_dist[dist] = depth;
        } else {
          new_min_depth_by_dist[dist] = min(it->second, depth);
        }
      }
      for (auto e : g[u]) {
        if (e.dst == parent || used[e.dst])
          continue;
        walk(u, e.dst, depth + 1, dist + e.len);
      }
    };

    for (auto e : g[centroid]) {
      if (used[e.dst])
        continue;
      comp_size = 0;
      walk(centroid, e.dst, 1, e.len);
      comp_sizes[e.dst] = comp_size;
      for (auto& [dist, depth] : new_min_depth_by_dist) {
        if (depth >= res)  // heuristic
          continue;
        i6 rem_dist = k - dist;
        if (rem_dist == 0) {
          assert(depth > 0);
          res = min(res, depth);
        } else if (rem_dist > 0) {
          auto it = min_depth_by_dist.find(rem_dist);
          if (it != min_depth_by_dist.end()) {
            assert(depth + it->second > 0);
            res = min(res, depth + it->second);
          }
        }
      }
      for (auto& [dist, depth] : new_min_depth_by_dist) {
        auto it = min_depth_by_dist.find(dist);
        if (it == min_depth_by_dist.end()) {
          min_depth_by_dist[dist] = depth;
        } else {
          min_depth_by_dist[dist] = min(it->second, depth);
        }
      }
      new_min_depth_by_dist.clear();
    }
  }

  for (auto e : g[centroid]) {
    compute_solution(e.dst, comp_sizes[e.dst]);
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  n = N;
  k = K;
  used.resize(N);
  g.resize(n);
  for (int i = 0; i < N - 1; i++) {
    g[H[i][0]].push_back({L[i], H[i][1]});
    g[H[i][1]].push_back({L[i], H[i][0]});
  }
  // for (int i = 0; i < N; i++) {
  //   cout << i << " -> ";
  //   for (auto e : g[i]) {
  //     cout << e.dst << " ";
  //   }
  //   cout << endl;
  // }
  compute_solution(0, n);
  return res == INT32_MAX ? -1 : res;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2552 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 2 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 1 ms 2488 KB Output is correct
12 Correct 1 ms 2552 KB Output is correct
13 Correct 1 ms 2384 KB Output is correct
14 Correct 1 ms 2552 KB Output is correct
15 Correct 1 ms 2384 KB Output is correct
16 Correct 1 ms 2640 KB Output is correct
17 Correct 1 ms 2384 KB Output is correct
18 Correct 1 ms 2384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2552 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 2 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 1 ms 2488 KB Output is correct
12 Correct 1 ms 2552 KB Output is correct
13 Correct 1 ms 2384 KB Output is correct
14 Correct 1 ms 2552 KB Output is correct
15 Correct 1 ms 2384 KB Output is correct
16 Correct 1 ms 2640 KB Output is correct
17 Correct 1 ms 2384 KB Output is correct
18 Correct 1 ms 2384 KB Output is correct
19 Correct 1 ms 2384 KB Output is correct
20 Correct 1 ms 2384 KB Output is correct
21 Correct 3 ms 2384 KB Output is correct
22 Correct 2 ms 2384 KB Output is correct
23 Correct 2 ms 2508 KB Output is correct
24 Correct 2 ms 2384 KB Output is correct
25 Correct 3 ms 2392 KB Output is correct
26 Correct 2 ms 2384 KB Output is correct
27 Correct 3 ms 2384 KB Output is correct
28 Correct 3 ms 2384 KB Output is correct
29 Correct 3 ms 2384 KB Output is correct
30 Correct 3 ms 2384 KB Output is correct
31 Correct 3 ms 2384 KB Output is correct
32 Correct 3 ms 2384 KB Output is correct
33 Correct 4 ms 2644 KB Output is correct
34 Correct 2 ms 2508 KB Output is correct
35 Correct 3 ms 2392 KB Output is correct
36 Correct 3 ms 2384 KB Output is correct
37 Correct 3 ms 2384 KB Output is correct
38 Correct 4 ms 2384 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2552 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 2 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 1 ms 2488 KB Output is correct
12 Correct 1 ms 2552 KB Output is correct
13 Correct 1 ms 2384 KB Output is correct
14 Correct 1 ms 2552 KB Output is correct
15 Correct 1 ms 2384 KB Output is correct
16 Correct 1 ms 2640 KB Output is correct
17 Correct 1 ms 2384 KB Output is correct
18 Correct 1 ms 2384 KB Output is correct
19 Execution timed out 3059 ms 12496 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2552 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 2 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 1 ms 2488 KB Output is correct
12 Correct 1 ms 2552 KB Output is correct
13 Correct 1 ms 2384 KB Output is correct
14 Correct 1 ms 2552 KB Output is correct
15 Correct 1 ms 2384 KB Output is correct
16 Correct 1 ms 2640 KB Output is correct
17 Correct 1 ms 2384 KB Output is correct
18 Correct 1 ms 2384 KB Output is correct
19 Correct 1 ms 2384 KB Output is correct
20 Correct 1 ms 2384 KB Output is correct
21 Correct 3 ms 2384 KB Output is correct
22 Correct 2 ms 2384 KB Output is correct
23 Correct 2 ms 2508 KB Output is correct
24 Correct 2 ms 2384 KB Output is correct
25 Correct 3 ms 2392 KB Output is correct
26 Correct 2 ms 2384 KB Output is correct
27 Correct 3 ms 2384 KB Output is correct
28 Correct 3 ms 2384 KB Output is correct
29 Correct 3 ms 2384 KB Output is correct
30 Correct 3 ms 2384 KB Output is correct
31 Correct 3 ms 2384 KB Output is correct
32 Correct 3 ms 2384 KB Output is correct
33 Correct 4 ms 2644 KB Output is correct
34 Correct 2 ms 2508 KB Output is correct
35 Correct 3 ms 2392 KB Output is correct
36 Correct 3 ms 2384 KB Output is correct
37 Correct 3 ms 2384 KB Output is correct
38 Correct 4 ms 2384 KB Output is correct
39 Execution timed out 3059 ms 12496 KB Time limit exceeded
40 Halted 0 ms 0 KB -