Submission #909548

#	Time	Username	Problem	Language	Result	Execution time	Memory
909548		rxlfd314	Highway Tolls (IOI18_highway)	C++17	12 / 100	251 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
 
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
 
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
 
void find_pair(int N, vt<int> U, vt<int> V, int A, int B) {
  const int M = size(U);
  vt<ari2> adj[N];
  FOR(i, 0, M-1) {
    adj[U[i]].push_back({V[i], i});
    adj[V[i]].push_back({U[i], i});
  }
  ll C = ask(vt<int>(M));
  vt<int> nodes[2];
  function<void(int, int, bool)> dfs = [&](int i, int p, bool c) {
    nodes[c].push_back(i);
    for (auto [j, _] : adj[i])
      if (j != p)
        dfs(j, i, !c);
  };
  dfs(0, 0, 0);
  vt<int> poss;
  if (C / A & 1) {
    poss = nodes[0];
    goto jail;
  }
  FOR(_, 0, 1) {
    FOR(b, 0, 31 - __builtin_clz(size(nodes[_]))) {
      vt<int> v(M);
      FOR(ii, 0, size(nodes[0])-1)
        if (ii & 1 << b) {
          int i = nodes[0][ii];
          poss.push_back(i);
          for (auto [__, j] : adj[i])
            v[j] = 1;
        }
      ll X = ask(v);
      int a = (X - C) / (B - A);
      if (a & 1)
        break;
      poss.clear();
    }
    if (size(poss))
      break;
  }
  jail:;
  #ifdef DEBUG
  cout << "possible:";
  for (int i : poss)
    cout << ' ' << i;
  cout << '\n';
  #endif
  int lo = 0, hi = size(poss) - 1;
  while (lo < hi) {
    int mid = lo + hi >> 1;
    vt<int> v(M);
    FOR(ii, 0, mid) {
      int i = poss[ii];
      for (auto [_, j] : adj[i])
        v[j] = 1;
    }
    ll X = ask(v);
    int a = (X - C) / (B - A);
    if (a & 1)
      hi = mid;
    else
      lo = mid + 1;
  }
  int ep = poss[lo];
  poss.clear();
  int par[N];
  function<void(int, int, int)> dfs2 = [&](int i, int p, int d) {
    if (d == C / A) {
      poss.push_back(i);
      return;
    }
    for (auto [j, ei] : adj[i])
      if (j != p) {
        par[j] = ei;
        dfs2(j, i, d + 1);
      }
  };
  dfs2(ep, ep, 0);
  lo = 0, hi = size(poss) - 1;
  while (lo < hi) {
    int mid = lo + hi >> 1;
    vt<int> v(M);
    FOR(ii, 0, mid) {
      int i = poss[ii];
      v[par[i]] = 1;
    }
    if (ask(v) != C)
      hi = mid;
    else
      lo = mid + 1;
  }
  answer(ep, poss[lo]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:64:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
highway.cpp:95:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |     int mid = lo + hi >> 1;
      |               ~~~^~~~

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