Submission #1244741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244741		Boas	Highway Tolls (IOI18_highway)	C++20	12 / 100	320 ms	327680 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define ALL(x) begin(x), end(x)
#define loop(n, i) for (int i = 0; i < n; i++)

typedef signed i32;
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<i32> vi32;
typedef vector<vi32> vvi32;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

void find_pair(i32 N, vi32 U, vi32 V, i32 A, i32 B)
{
  vvii adj(N);
  int M = sz(U);
  loop(M, i)
  {
    adj[U[i]].pb({V[i], i});
    adj[V[i]].pb({U[i], i});
  }
  int disST = ask(vi32(M, 0)) / A;
  vi dis(N);
  vii cand;
  auto dfs = [&](auto &&self, int i, int prev) -> void
  {
    for (auto [j, ix] : adj[i])
      if (j != prev)
      {
        dis[j] = dis[i] + 1;
        if (dis[j] == disST)
          cand.pb({j, ix});
        self(self, j, i);
      }
  };
  dfs(dfs, 0, 0);
  int lo = 0, hi = sz(cand);
  while (hi > lo)
  {
    int m = (lo + hi) / 2;
    vi32 q(M);
    for (int i = 0; i <= m; i++)
      q[cand[i].second] = 1;
    if (ask(q) > disST * (i64)A)
      hi = m;
    else
      lo = m + 1;
  }
  answer(0, cand[lo].first);
}

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