oj.uz

Submission #967247

# Submission time Handle Problem Language Result Execution time Memory
967247 2024-04-21T15:40:51 Z kilkuwu Highway Tolls (IOI18_highway) C++17
100 / 100
 195 ms 12860 KB 
#include "highway.h"
#include <bits/stdc++.h>

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

std::vector<int> bfs(int s, const std::vector<std::vector<std::pair<int, int>>>& adj) {
  int N = adj.size();
  std::vector<int> d(N, -1);
  std::queue<int> q;
  q.push(s);

  d[s] = 0;
  while (q.size()) {
    int u = q.front();
    q.pop();

    for (auto [v, id] : adj[u]) {
      if (d[v] == -1) { 
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }

  return d;
}

std::vector<std::pair<int, int>> build_tree(int s, const std::vector<std::vector<std::pair<int, int>>>& adj, const std::vector<int>& d1, const std::vector<int>& d2) {
  int N = adj.size();
  std::vector<std::pair<int, int>> tree;
  std::vector<int> d(N, -1);

  std::queue<int> q;
  q.push(s);

  d[s] = 0;
  while (q.size()) {
    int u = q.front();
    q.pop();

    for (auto [v, id] : adj[u]) {
      if (d1[v] < d2[v] && d[v] == -1) { 
        tree.emplace_back(v, id);
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }

  return tree;
}

int solve(int s, int M, long long sd, const std::vector<std::pair<int, int>>& trees, const std::vector<int>& unused) {
  int ans = s, lb = 0, rb = trees.size() - 1;
  while (lb <= rb) {
    int m = (lb + rb) / 2;
    std::vector<int> w(M, 0);
    for (int j = m; j < (int) trees.size(); j++) {
      w[trees[j].second] = 1;
    }
    for (int i : unused) {
      w[i] = 1;
    }
    auto res = ask(w);
    if (res != sd) {
      ans = trees[m].first;
      lb = m + 1;
    } else {
      rb = m - 1;
    }
  }
  return ans;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  std::vector<std::vector<std::pair<int, int>>> adj(N);
  int M = U.size();
  for (int i = 0; i < M; i++) {
    adj[U[i]].emplace_back(V[i], i);
    adj[V[i]].emplace_back(U[i], i);
  }

  auto shortest_distance = ask(std::vector<int>(M, 0));
  int first_in_path = -1;
  int lb = 0, rb = M - 1;
  while (lb <= rb) {
    int m = (lb + rb) / 2;
    auto nice = std::vector<int>(M, 0);
    std::fill(nice.begin(), nice.begin() + m + 1, 1);
    auto aa = ask(nice);
    if (aa != shortest_distance) {
      first_in_path = m;
      rb = m - 1;
    } else {
      lb = m + 1;
    }
  }
  dbg(first_in_path);

  auto a = U[first_in_path];
  auto b = V[first_in_path];
  dbg(a, b);
  auto d1 = bfs(a, adj);
  auto d2 = bfs(b, adj);
  auto treea = build_tree(a, adj, d1, d2);
  auto treeb = build_tree(b, adj, d2, d1);
  std::vector<int> used(M);
  for (auto [x, y] : treea) {
    used[y] = 1;
  }
  for (auto [x, y] : treeb) {
    used[y] = 1;
  }
  used[first_in_path] = 1;
  std::vector<int> unused;
  for (int i = 0; i < M; i++) {
    if (!used[i]) unused.push_back(i);
  }
  auto ff = solve(a, M, shortest_distance, treea, unused);
  auto ee = solve(b, M, shortest_distance, treeb, unused);
  answer(ff, ee);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 448 KB Output is correct
4 Correct 0 ms 444 KB Output is correct
5 Correct 0 ms 444 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 0 ms 440 KB Output is correct
9 Correct 0 ms 444 KB Output is correct
10 Correct 0 ms 440 KB Output is correct
11 Correct 0 ms 440 KB Output is correct
12 Correct 1 ms 440 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 10 ms 1540 KB Output is correct
3 Correct 132 ms 9848 KB Output is correct
4 Correct 89 ms 9872 KB Output is correct
5 Correct 103 ms 9872 KB Output is correct
6 Correct 108 ms 9720 KB Output is correct
7 Correct 96 ms 10220 KB Output is correct
8 Correct 93 ms 9716 KB Output is correct
9 Correct 107 ms 9716 KB Output is correct
10 Correct 85 ms 9848 KB Output is correct
11 Correct 144 ms 9272 KB Output is correct
12 Correct 94 ms 9708 KB Output is correct
13 Correct 110 ms 9284 KB Output is correct
14 Correct 108 ms 9464 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1576 KB Output is correct
2 Correct 24 ms 2404 KB Output is correct
3 Correct 22 ms 3304 KB Output is correct
4 Correct 88 ms 9204 KB Output is correct
5 Correct 95 ms 9056 KB Output is correct
6 Correct 122 ms 9664 KB Output is correct
7 Correct 71 ms 9168 KB Output is correct
8 Correct 80 ms 9148 KB Output is correct
9 Correct 71 ms 9220 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 8 ms 1740 KB Output is correct
3 Correct 70 ms 7752 KB Output is correct
4 Correct 98 ms 9716 KB Output is correct
5 Correct 82 ms 9716 KB Output is correct
6 Correct 122 ms 9716 KB Output is correct
7 Correct 77 ms 9968 KB Output is correct
8 Correct 97 ms 9712 KB Output is correct
9 Correct 85 ms 9816 KB Output is correct
10 Correct 95 ms 10080 KB Output is correct
11 Correct 87 ms 9284 KB Output is correct
12 Correct 87 ms 9512 KB Output is correct
13 Correct 93 ms 9484 KB Output is correct
14 Correct 123 ms 9380 KB Output is correct
15 Correct 83 ms 9840 KB Output is correct
16 Correct 80 ms 9728 KB Output is correct
17 Correct 115 ms 9448 KB Output is correct
18 Correct 89 ms 9248 KB Output is correct
19 Correct 102 ms 9720 KB Output is correct
20 Correct 126 ms 9428 KB Output is correct
21 Correct 67 ms 10156 KB Output is correct
22 Correct 91 ms 10136 KB Output is correct
23 Correct 76 ms 10028 KB Output is correct
24 Correct 100 ms 9692 KB Output is correct
25 Correct 114 ms 9376 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1636 KB Output is correct
2 Correct 12 ms 1604 KB Output is correct
3 Correct 116 ms 10448 KB Output is correct
4 Correct 131 ms 11128 KB Output is correct
5 Correct 170 ms 12408 KB Output is correct
6 Correct 125 ms 12860 KB Output is correct
7 Correct 142 ms 12188 KB Output is correct
8 Correct 122 ms 12348 KB Output is correct
9 Correct 120 ms 8592 KB Output is correct
10 Correct 120 ms 8656 KB Output is correct
11 Correct 104 ms 9156 KB Output is correct
12 Correct 142 ms 11724 KB Output is correct
13 Correct 182 ms 11772 KB Output is correct
14 Correct 152 ms 12204 KB Output is correct
15 Correct 139 ms 12400 KB Output is correct
16 Correct 126 ms 9624 KB Output is correct
17 Correct 82 ms 9972 KB Output is correct
18 Correct 80 ms 10540 KB Output is correct
19 Correct 90 ms 10056 KB Output is correct
20 Correct 89 ms 10260 KB Output is correct
21 Correct 177 ms 12256 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1540 KB Output is correct
2 Correct 14 ms 1836 KB Output is correct
3 Correct 123 ms 10384 KB Output is correct
4 Correct 134 ms 10524 KB Output is correct
5 Correct 136 ms 10760 KB Output is correct
6 Correct 150 ms 11940 KB Output is correct
7 Correct 110 ms 10132 KB Output is correct
8 Correct 156 ms 10680 KB Output is correct
9 Correct 149 ms 10904 KB Output is correct
10 Correct 152 ms 11964 KB Output is correct
11 Correct 150 ms 11932 KB Output is correct
12 Correct 141 ms 11964 KB Output is correct
13 Correct 150 ms 8916 KB Output is correct
14 Correct 126 ms 8652 KB Output is correct
15 Correct 113 ms 9128 KB Output is correct
16 Correct 78 ms 8652 KB Output is correct
17 Correct 93 ms 8920 KB Output is correct
18 Correct 96 ms 8928 KB Output is correct
19 Correct 119 ms 11512 KB Output is correct
20 Correct 130 ms 11736 KB Output is correct
21 Correct 158 ms 12460 KB Output is correct
22 Correct 152 ms 12176 KB Output is correct
23 Correct 124 ms 12568 KB Output is correct
24 Correct 134 ms 12228 KB Output is correct
25 Correct 145 ms 12560 KB Output is correct
26 Correct 134 ms 12260 KB Output is correct
27 Correct 79 ms 10104 KB Output is correct
28 Correct 77 ms 10124 KB Output is correct
29 Correct 101 ms 10320 KB Output is correct
30 Correct 83 ms 10188 KB Output is correct
31 Correct 98 ms 10040 KB Output is correct
32 Correct 82 ms 10056 KB Output is correct
33 Correct 109 ms 10208 KB Output is correct
34 Correct 132 ms 10144 KB Output is correct
35 Correct 77 ms 10272 KB Output is correct
36 Correct 89 ms 9936 KB Output is correct
37 Correct 88 ms 10576 KB Output is correct
38 Correct 70 ms 10316 KB Output is correct
39 Correct 195 ms 12460 KB Output is correct
40 Correct 172 ms 12476 KB Output is correct
41 Correct 177 ms 12560 KB Output is correct
42 Correct 157 ms 12648 KB Output is correct