Submission #1152968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152968		fryingduc	Highway Tolls (IOI18_highway)	C++20	90 / 100	110 ms	9544 KiB

highway

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

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
  assert(l <= r);
  return uniform_int_distribution<int> (l, r)(rng);
}

const int maxn = 1e5 + 5;
int n, m, a, b;
int d[maxn], ord[maxn];
vector<int> g[maxn];
bool mark[maxn];

void bfs(int src) {
  queue<int> q;
  memset(d, 0x3f, sizeof(d));
  d[src] = 0;
  q.push(src);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto v:g[u]) {
      if (d[v] > d[u] + 1) {
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  a = A, b = B;
  n = N;
  int m = (int)U.size();
  for (int i = 0; i < m; ++i) {
    g[U[i]].push_back(V[i]);
    g[V[i]].push_back(U[i]);
  }
  vector<int> hehe(m, 0); 
  long long ft_dist = ask(hehe);
  int l = 0, r = m - 1, e = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    for (int i = 0; i <= mid; ++i) {
      hehe[i] = 1;
    }
    for (int i = mid + 1; i < m; ++i) {
      hehe[i] = 0;
    }
    long long x = ask(hehe);
    if (x != ft_dist) {
      e = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  assert(e != -1);
  int u = U[e];
  iota(ord, ord + n, 0);
  bfs(u);
  sort(ord, ord + n, [](const int &x, const int &y) -> bool {
    return d[x] < d[y];
  });
//  debug(u);
  l = 0, r = n - 1;
  int s = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    for (int i = 0; i < m; ++i) {
      hehe[i] = 0;
    }
    for (int i = mid + 1; i < n; ++i) {
      mark[ord[i]] = 1;
    }
    for (int i = 0; i < m; ++i) {
      if (mark[U[i]] || mark[V[i]]) {
        hehe[i] = 1;
      }
    }
    long long x = ask(hehe);
//    debug(u, mid, ord[mid], hehe, x);
    if (x == ft_dist) {
      s = ord[mid];
      r = mid - 1;
    } else {
      l = mid + 1;
    }
    for (int i = mid + 1; i < n; ++i) {
      mark[ord[i]] = 0;
    }
  }
  assert(s != -1);
  u = s;
//  debug(s);
  bfs(s);
  vector<int> vec;
  for (int i = 0; i < n; ++i) {
    if (d[i] == ft_dist / a) {
      vec.push_back(i);
    }
  }
  shuffle(vec.begin(), vec.end(), rng);
  l = 0, r = (int)vec.size() - 1;
  int t = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    for (int i = 0; i < m; ++i) hehe[i] = 0;
    for (int i = mid + 1; i < (int)vec.size(); ++i) {
      mark[vec[i]] = 1;
    }
    for (int i = 0; i < m; ++i) {
      if (mark[U[i]] || mark[V[i]]) {
        hehe[i] = 1;
      }
    }
    long long x = ask(hehe);
    if (x == ft_dist) {
      t = vec[mid];
      r = mid - 1;
    } else {
      l = mid + 1;
    }
    for (int i = mid + 1; i < (int)vec.size(); ++i) {
      mark[vec[i]] = 0;
    }
  }
//  debug(s, t);
  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