oj.uz

Submission #967238

# Submission time Handle Problem Language Result Execution time Memory
967238 2024-04-21T14:50:10 Z kilkuwu Highway Tolls (IOI18_highway) C++17
51 / 100
 159 ms 13548 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) {
  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;
    }
    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;
    }
  }

  auto a = U[first_in_path];
  auto b = V[first_in_path];
  auto d1 = bfs(a, adj);
  auto d2 = bfs(b, adj);
  auto treea = build_tree(a, adj, d1, d2);
  std::set<int> fff;
  for (auto [x, y] : treea) fff.insert(y), assert(y != first_in_path);
  auto treeb = build_tree(b, adj, d2, d1);
  for (auto [x, y] : treeb) {
    assert(!fff.count(y));
    assert(y != first_in_path);
  }
  auto ff = solve(a, M, shortest_distance, treea);
  auto ee = solve(b, M, shortest_distance, treeb);
  answer(ff, ee);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 444 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 0 ms 444 KB Output is correct
9 Correct 0 ms 444 KB Output is correct
10 Correct 0 ms 440 KB Output is correct
11 Correct 1 ms 448 KB Output is correct
12 Correct 0 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 11 ms 1864 KB Output is correct
3 Correct 137 ms 13536 KB Output is correct
4 Correct 141 ms 10212 KB Output is correct
5 Correct 102 ms 9740 KB Output is correct
6 Correct 97 ms 10212 KB Output is correct
7 Correct 127 ms 10248 KB Output is correct
8 Correct 91 ms 10084 KB Output is correct
9 Correct 103 ms 13548 KB Output is correct
10 Correct 100 ms 9856 KB Output is correct
11 Correct 124 ms 11752 KB Output is correct
12 Correct 142 ms 12220 KB Output is correct
13 Correct 89 ms 9424 KB Output is correct
14 Correct 158 ms 12744 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1800 KB Output is correct
2 Correct 18 ms 2552 KB Output is correct
3 Correct 27 ms 4424 KB Output is correct
4 Correct 70 ms 10664 KB Output is correct
5 Correct 88 ms 10628 KB Output is correct
6 Correct 71 ms 10192 KB Output is correct
7 Correct 116 ms 12604 KB Output is correct
8 Correct 79 ms 10296 KB Output is correct
9 Correct 116 ms 11932 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 12 ms 1508 KB Output is correct
3 Correct 64 ms 8004 KB Output is correct
4 Correct 94 ms 9736 KB Output is correct
5 Correct 107 ms 13316 KB Output is correct
6 Correct 108 ms 9716 KB Output is correct
7 Correct 117 ms 13320 KB Output is correct
8 Correct 114 ms 13308 KB Output is correct
9 Correct 107 ms 13276 KB Output is correct
10 Correct 110 ms 13240 KB Output is correct
11 Correct 132 ms 12936 KB Output is correct
12 Correct 134 ms 9936 KB Output is correct
13 Correct 130 ms 12168 KB Output is correct
14 Correct 101 ms 11552 KB Output is correct
15 Correct 76 ms 9716 KB Output is correct
16 Correct 113 ms 9720 KB Output is correct
17 Correct 112 ms 12452 KB Output is correct
18 Correct 135 ms 12860 KB Output is correct
19 Correct 139 ms 13328 KB Output is correct
20 Correct 115 ms 10168 KB Output is correct
21 Correct 99 ms 10376 KB Output is correct
22 Correct 95 ms 13476 KB Output is correct
23 Correct 113 ms 12104 KB Output is correct
24 Correct 92 ms 12108 KB Output is correct
25 Correct 122 ms 13036 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1560 KB Output is correct
2 Correct 19 ms 2040 KB Output is correct
3 Correct 134 ms 10324 KB Output is correct
4 Correct 134 ms 13108 KB Output is correct
5 Correct 138 ms 11960 KB Output is correct
6 Correct 129 ms 11928 KB Output is correct
7 Correct 136 ms 12144 KB Output is correct
8 Incorrect 150 ms 13124 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1932 KB Output is correct
2 Correct 14 ms 2192 KB Output is correct
3 Correct 135 ms 11904 KB Output is correct
4 Correct 159 ms 11472 KB Output is correct
5 Correct 120 ms 11152 KB Output is correct
6 Correct 127 ms 13156 KB Output is correct
7 Correct 103 ms 10188 KB Output is correct
8 Correct 142 ms 10780 KB Output is correct
9 Incorrect 142 ms 12388 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -