Submission #1081789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081789		erray	Highway Tolls (IOI18_highway)	C++17	90 / 100	174 ms	10412 KiB

highway

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

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/contests/ioi18_d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

template<typename F = function<bool(const int&)>>
int find_first(int l, int r, F good) {
  ++r;
  int bad = r;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (!good(mid)) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  return (l == bad ? -1 : l);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  int M = 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);
  }
  /*
  for (int j = 0; j < 50; ++j) {
    std::vector<int> w(M);
    for (int i = 0; i < M; ++i) {
      w[i] = 0;
    }
    long long toll = ask(w);
  }
  answer(0, N - 1);
  */
  int64_t small = ask(vector<int>(M, 0));
  int on_path = find_first(0, N - 1, [&](int m) {
    vector<int> w(M, 0);
    for (int i = 0; i <= m; ++i) {
      for (auto id : g[i]) w[id] = 1;
    }
    int64_t g = ask(w);
    return g != small;
  });
  assert(on_path != -1);
  debug(on_path);
  //you can predetermine if it's S or T but ignore it for now 
  vector<int> que;
  vector<bool> vis(N);
  vector<int> par(N, -1);
  vis[on_path] = true;
  que.push_back(on_path);
  vector<int> start_w(M, 1);
  for (int it = 0; it < int(que.size()); ++it) {
    int v = que[it];
    for (auto id : g[v]) {
      int u = v ^ V[id] ^ U[id];
      if (!vis[u]) {
        vis[u] = true;
        start_w[id] = 0;
        par[u] = v;
        vis[u] = true;
        que.push_back(u);
      }
    }
  }
  auto ord = que;
  reverse(ord.begin(), ord.end());
  int S = ord[find_first(0, N - 2, [&](int m) {
    auto w = start_w;
    for (int i = 0; i <= m; ++i) {
      for (auto id : g[ord[i]]) w[id] = 1;
    }
    int64_t g = ask(w);
    return g != small;
  })];
  debug(S);
  vector<bool> rem(N);
  {
    int v = S;
    while (v != -1) {
      rem[v] = true;
      v = par[v];
    }
  }
  {
    vector<int> new_ord;
    for (auto v : ord) {
      if (!rem[v]) {
        new_ord.push_back(v);
      }
    }
    swap(ord, new_ord);
  }
  debug(ord);
  int Q_ind = find_first(0, int(ord.size()) - 1, [&](int m) {
    auto w = start_w;
    for (int i = 0; i <= m; ++i) {
      for (auto id : g[ord[i]]) w[id] = 1;
    }
    int64_t g = ask(w);
    return g != small;
  });
  debug(Q_ind);
  if (Q_ind == -1) {
    answer(S, on_path);
  } else {
    answer(S, ord[Q_ind]);
  }
}

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