제출 #967233

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
967233		kilkuwu	통행료 (IOI18_highway)	C++17	51 / 100	179 ms	11880 KiB

highway

#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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31