Submission #606653

#	Time	Username	Problem	Language	Result	Execution time	Memory
606653		piOOE	Highway Tolls (IOI18_highway)	C++17	100 / 100	282 ms	11256 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

using ll = long long;

void find_pair(int n, vector<int> A, vector<int> B, int a, int b) {
  //I am so stupid, my binary search was wrong qwq

  int m = (int) B.size();

  const ll val = ask(vector<int>(m));

  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; ++i) {
    g[A[i]].push_back({B[i], i});
    g[B[i]].push_back({A[i], i});
  }

  int low = 0, high = m;
  while (low + 1 < high) {
    int mid = (low + high) >> 1;
    vector<int> now(m, 1);
    fill(now.begin(), now.begin() + mid, 0);
    if (ask(now) == val) {
      high = mid;
    } else {
      low = mid;
    }
  }

  int e = low;
  int u = A[e], v = B[e];

  vector<int> S, T, root(n), dep(n, -1), par(n, -1);
  queue<int> q;
  q.push(root[u] = u), q.push(root[v] = v);
  par[u] = par[v] = e;
  dep[u] = dep[v] = 0;
  S.push_back(u), T.push_back(v);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (auto [to, i]: g[x]) {
      if (dep[to] == -1) {
        dep[to] = dep[x] + 1;
        root[to] = root[x];
        par[to] = i;
        q.push(to);
        if (root[to] == u) {
          S.push_back(to);
        } else {
          T.push_back(to);
        }
      }
    }
  }

  auto solve = [&](const vector<int> &t1, const vector<int> &t2) {
    int l = 0, r = (int) t1.size();
    while (l + 1 < r) {
      int mid = (l + r) >> 1;
      vector<int> now(m, 1);
      for (int x : t2) {
        now[par[x]] = 0;
      }
      for (int i = 0; i < mid; ++i) {
        now[par[t1[i]]] = 0;
      }
      if (ask(now) == val) {
        r = mid;
      } else {
        l = mid;
      }
    }
    return t1[l];
  };

  answer(solve(S, T), solve(T, S));
}			

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