oj.uz

Submission #967245

# Submission time Handle Problem Language Result Execution time Memory
967245 2024-04-21T15:39:33 Z kilkuwu Highway Tolls (IOI18_highway) C++17
0 / 100
 13 ms 1800 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;
  }
  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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 444 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 516 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1488 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 768 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1800 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1540 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -