Submission #1216347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216347		not_amir	Highway Tolls (IOI18_highway)	C++20	100 / 100	144 ms	11580 KiB

highway

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

typedef pair<int, int> pii;

vector<vector<pii>> G;

vector<int> dist(int N, int v) {
  vector<bool> vis(N);
  vector<int> dist(N);
  queue<pii> q;
  q.push({v, 0});
  while (!q.empty()) {
    auto [v,d] = q.front();
    q.pop();
    if (vis[v])
      continue;
    vis[v] = true;
    dist[v] = d;
    for (auto [u, i] : G[v])
      if (!vis[u]) q.push({u, d + 1});
  }
  return dist;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  assert(U.size() == V.size());
  int M = U.size();
  G.resize(N);
  for (int i = 0; i < M; i++)
    G[U[i]].push_back({V[i], i}), G[V[i]].push_back({U[i], i});
  vector<int> w(M);
  long long base = ask(w);
  int l = 0, r = M - 1, a = 0;
  while (l <= r) {
    int m = (l + r) / 2;
    w = vector<int>(M);
    for (int i = 0; i < M; i++)
      w[i] = i < m;
    if (ask(w) == base)
      a = m, l = m + 1;
    else
      r = m - 1;
  }
  vector<int> p;
  array d = {dist(N, U[a]), dist(N, V[a])};
  for (int v : {U[a], V[a]}) {
    vector<int> ord;
    for (int i = 0; i < N; i++)
      if (d[0][i] < d[1][i])
        ord.push_back(i);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
      return d[0][i] > d[0][j];
    });
    int cur = 0;
    l = 0, r = ord.size() - 1;
    while (l <= r) {
      int m = (l + r) / 2;
      w = vector<int>(M);
      for (int i = 0; i < a; i++)
        w[i] = 1;
      for (int i = 0; i < m; i++) {
        for (auto [u, idx] : G[ord[i]])
          w[idx] = 1;
      }
      if (ask(w) == base)
        l = m + 1, cur = ord[m];
      else
        r = m - 1;
    }
    swap(d[0], d[1]);
    p.push_back(cur);
  }
  answer(p[0], p[1]);
}

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