Submission #605350

#	Time	Username	Problem	Language	Result	Execution time	Memory
605350		piOOE	Highway Tolls (IOI18_highway)	C++17	90 / 100	270 ms	19712 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) {
  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});
  }

  function<int(vector<int>)> bin_search = [&](const vector<int> &v) -> int {
    if (v.size() == 1) {
      return v[0];
    }
    int sz = (int) v.size();
    assert(sz > 0);
    int mid = int(v.size() >> 1);
    vector<int> L(mid), R(sz - mid);
    for (int i = 0; i < mid; ++i) {
      L[i] = v[i];
    }
    for (int i = mid; i < sz; ++i) {
      R[i - mid] = v[i];
    }
    vector<int> nxt(m, 0);
    for (int x: R) {
      for (auto [to, i]: g[x]) {
        nxt[i] = 1;
      }
    }
    ll now = ask(nxt);
    if (now == val) {
      return bin_search(L);
    } else {
      return bin_search(R);
    }
  };

  auto solve = [&](int s) {
    //solves for tree with known S
    int len = val / a;
    vector<int> depth(n, -1);
    depth[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (auto [to, i]: g[v]) {
        if (depth[to] == -1) {
          depth[to] = depth[v] + 1;
          q.push(to);
        }
      }
    }
    vector<int> canditates;
    for (int i = 0; i < n; ++i) {
      if (depth[i] == len) {
        canditates.push_back(i);
      }
    }
    answer(s, bin_search(canditates));
  };

  vector<int> u(n);
  iota(u.begin(), u.end(), 0);

  mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


  //
  if (a == 1 && b == 2)
    shuffle(u.begin(), u.end(), rnd);

  int mid = bin_search(u);

  vector<int> depth(n, -1);
  depth[mid] = 0;
  queue<int> q;
  q.push(mid);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (auto [to, i]: g[v]) {
      if (depth[to] == -1) {
        depth[to] = depth[v] + 1;
        q.push(to);
      }
    }
  }
  sort(u.begin(), u.end(), [&depth](int i, int j) {
    return depth[i] < depth[j];
  });
  solve(bin_search(u));
}

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