oj.uz

Submission #967233

# Submission time Handle Problem Language Result Execution time Memory
967233 2024-04-21T14:37:45 Z kilkuwu Highway Tolls (IOI18_highway) C++17
51 / 100
 179 ms 11880 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 = M - 1;
  int lb = 0, rb = M - 2;
  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);
  auto treeb = build_tree(b, adj, d2, d1);
  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 0 ms 448 KB Output is correct
2 Correct 0 ms 448 KB Output is correct
3 Correct 0 ms 444 KB Output is correct
4 Correct 0 ms 444 KB Output is correct
5 Correct 0 ms 444 KB Output is correct
6 Correct 0 ms 444 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 0 ms 444 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 444 KB Output is correct
11 Correct 0 ms 440 KB Output is correct
12 Correct 1 ms 444 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 772 KB Output is correct
2 Correct 16 ms 1724 KB Output is correct
3 Correct 98 ms 9956 KB Output is correct
4 Correct 87 ms 9732 KB Output is correct
5 Correct 98 ms 9724 KB Output is correct
6 Correct 120 ms 9804 KB Output is correct
7 Correct 111 ms 10108 KB Output is correct
8 Correct 84 ms 9728 KB Output is correct
9 Correct 104 ms 9748 KB Output is correct
10 Correct 86 ms 10092 KB Output is correct
11 Correct 92 ms 9276 KB Output is correct
12 Correct 98 ms 9176 KB Output is correct
13 Correct 92 ms 9772 KB Output is correct
14 Correct 77 ms 9224 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1572 KB Output is correct
2 Correct 16 ms 2380 KB Output is correct
3 Correct 41 ms 3496 KB Output is correct
4 Correct 74 ms 9048 KB Output is correct
5 Correct 81 ms 9296 KB Output is correct
6 Correct 62 ms 9844 KB Output is correct
7 Correct 66 ms 9168 KB Output is correct
8 Correct 101 ms 9296 KB Output is correct
9 Correct 89 ms 9184 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 11 ms 1488 KB Output is correct
3 Correct 57 ms 7752 KB Output is correct
4 Correct 78 ms 9856 KB Output is correct
5 Correct 86 ms 9984 KB Output is correct
6 Correct 97 ms 9720 KB Output is correct
7 Correct 86 ms 9720 KB Output is correct
8 Correct 103 ms 9996 KB Output is correct
9 Correct 126 ms 9812 KB Output is correct
10 Correct 81 ms 9724 KB Output is correct
11 Correct 122 ms 9360 KB Output is correct
12 Correct 92 ms 9596 KB Output is correct
13 Correct 86 ms 9616 KB Output is correct
14 Correct 99 ms 9032 KB Output is correct
15 Correct 81 ms 9864 KB Output is correct
16 Correct 100 ms 9968 KB Output is correct
17 Correct 82 ms 9220 KB Output is correct
18 Correct 83 ms 9260 KB Output is correct
19 Correct 104 ms 9916 KB Output is correct
20 Correct 103 ms 9428 KB Output is correct
21 Correct 67 ms 10136 KB Output is correct
22 Correct 90 ms 10064 KB Output is correct
23 Correct 75 ms 9772 KB Output is correct
24 Correct 98 ms 9716 KB Output is correct
25 Correct 86 ms 9264 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1600 KB Output is correct
2 Correct 12 ms 1668 KB Output is correct
3 Correct 90 ms 10152 KB Output is correct
4 Correct 137 ms 10444 KB Output is correct
5 Correct 131 ms 11636 KB Output is correct
6 Correct 148 ms 11880 KB Output is correct
7 Correct 179 ms 11268 KB Output is correct
8 Incorrect 146 ms 11592 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 12 ms 1576 KB Output is correct
2 Correct 11 ms 1668 KB Output is correct
3 Correct 112 ms 10796 KB Output is correct
4 Correct 107 ms 10264 KB Output is correct
5 Correct 128 ms 10704 KB Output is correct
6 Correct 112 ms 11016 KB Output is correct
7 Correct 103 ms 10224 KB Output is correct
8 Correct 98 ms 10552 KB Output is correct
9 Incorrect 124 ms 10176 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -