Submission #823355

#	Time	Username	Problem	Language	Result	Execution time	Memory
823355		KoD	Highway Tolls (IOI18_highway)	C++17	90 / 100	302 ms	9052 KiB

highway

#include "highway.h"

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <tuple>
#include <utility>

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

using std::begin;
using std::end;

using ll = long long;
constexpr int inf = 1 << 30;
constexpr ll infll = (1ll << 62) - 1;

template <class F> int binary_search(int ok, int ng, const F& f) {
  while (std::abs(ok - ng) > 1) {
    const int md = (ok + ng) / 2;
    (f(md) ? ok : ng) = md;
  }
  return ok;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  const int M = (int)U.size();
  vector<vector<int>> G(N);
  for (int i = 0; i < M; ++i) {
    G[U[i]].push_back(i);
    G[V[i]].push_back(i);
  }
  const auto bfs_order = [&](int src) {
    vector<int> ret;
    vector<char> done(N);
    std::queue<int> que;
    ret.reserve(N);
    const auto push = [&](int u) {
      if (!done[u]) {
        done[u] = true;
        ret.push_back(u);
        que.push(u);
      }
    };
    push(src);
    while (!que.empty()) {
      const int u = que.front();
      que.pop();
      for (const int e : G[u]) {
        push(u ^ U[e] ^ V[e]);
      }
    }
    return ret;
  };
  const ll best = ask(vector(M, 0));
  const int P = binary_search(0, N, [&](int thres) -> bool {
    vector<int> w(M);
    for (int i = 0; i < thres; ++i) {
      for (const int e : G[i]) w[e] = 1;
    }
    return ask(w) == best;
  });
  const auto ordP = bfs_order(P);
  const int S = ordP[binary_search(N, 0, [&](int thres) -> bool {
    vector<int> w(M);
    for (int i = thres; i < N; ++i) {
      for (const int e : G[ordP[i]]) w[e] = 1;
    }
    return ask(w) == best;
  }) - 1];
  const auto ordS = bfs_order(S);
  const int T = ordS[binary_search(N, 0, [&](int thres) -> bool {
    vector<int> w(M);
    for (int i = thres; i < N; ++i) {
      for (const int e : G[ordS[i]]) w[e] = 1;
    }
    return ask(w) == best;
  }) - 1];
  answer(S, T);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 21 / 31