Submission #823367

#	Time	Username	Problem	Language	Result	Execution time	Memory
823367		KoD	Highway Tolls (IOI18_highway)	C++17	100 / 100	206 ms	8936 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

template <class F> int binary_search(int ok, int ng, int md, const F& f) {
  while (abs(ok - ng) > 1) {
    (f(md) ? ok : ng) = md;
    md = (ok + ng) / 2;
  }
  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);
  }
  vector<char> dead(N);
  const auto bfs_order = [&](int src) {
    vector<int> ret;
    vector<char> done(N);
    queue<int> que;
    ret.reserve(N);
    const auto push = [&](int u) {
      if (!dead[u] && !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 long long best = ask(vector(M, 0));
  const int P = binary_search(0, N, N / 3, [&](int thres) {
    vector<int> w(M);
    for (int i = 0; i < thres; ++i) {
      for (const int e : G[i]) w[e] = 1;
    }
    return ask(w) == best;
  });
  for (int i = 0; i < P; ++i) dead[i] = true;
  const int S = [&] {
    const auto ord = bfs_order(P);
    const int n = (int)ord.size();
    const int k = binary_search(n, 0, 2 * n / 3, [&](int thres) {
      vector<int> w(M);
      for (int i = thres; i < n; ++i) {
        for (const int e : G[ord[i]]) w[e] = 1;
      }
      for (int i = 0; i < N; ++i) {
        if (dead[i]) {
          for (const int e : G[i]) w[e] = 1;
        }
      }
      return ask(w) == best;
    });
    for (int i = k; i < n; ++i) dead[ord[i]] = true;
    return ord[k - 1];
  }();
  const int T = [&] {
    const auto ord = bfs_order(S);
    const int n = (int)ord.size();
    const int k = binary_search(n, 0, 2 * n / 3, [&](int thres) {
      vector<int> w(M);
      for (int i = thres; i < n; ++i) {
        for (const int e : G[ord[i]]) w[e] = 1;
      }
      for (int i = 0; i < N; ++i) {
        if (dead[i]) {
          for (const int e : G[i]) w[e] = 1;
        }
      }
      return ask(w) == best;
    });
    for (int i = k; i < n; ++i) dead[ord[i]] = true;
    return ord[k - 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: 31 / 31