Submission #768221

#	Time	Username	Problem	Language	Result	Execution time	Memory
768221		coloboxx	Highway Tolls (IOI18_highway)	C++17	5 / 100	117 ms	29448 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define point pair<int, int>
#define pb push_back
#define show(x) cerr << (#x) << " = " << x << '\n'

using namespace std;

const int N = 1 << 18;

int n, a, b, len;
vector<point> g[N];
vector<point> e;

#define int ll

int norm(int s) {
//      show(s);
      return (s - a * len) / (b - a);
}

int Q = 0;

int query(vector<signed> v) {
      ++Q;
      if (Q >= 60)
            while(true) {}
      int res = norm(ask(v));
      return res;
}

vector<int> lst;

void dfs(int v, int pr, int dist, int target) {
//      show(v);
      assert(v < N && v >= 0);
      for (auto [to, id] : g[v]) {
            if (to == pr)
                  continue;

//            show(v), show(to);

            if (e[id].first != v)
                  swap(e[id].first, e[id].second);

            if (target == -1 || target == dist + 1) {
                  lst.pb(id);
            }

            dfs(to, v, dist + 1, target);
      }
}

int solve_rooted(int root, int pr) {
//      show(root), show(pr);
      dfs(root, pr, 0, -1);

      assert(!lst.empty());

//      show(lst.size());

      vector<signed> f(n - 1);
      for (int x : lst)
            f[x] = true;

      int p = query(f);
//      show(p);
      if (p == 0)
            return root;

      lst.clear();
      dfs(root, pr, 0, p);
      assert(!lst.empty());

      int l = 0, r = lst.size() - 1;
      while (l < r) {
            int mid = (l + r) >> 1;
            vector<signed> v(n - 1);
            for (int i = l; i <= mid; ++i)
                  v[lst[i]] = true;

            if (query(v))
                  r = mid;
            else
                  l = mid + 1;
      }

//      show(l), show(r);

      return e[lst[l]].second;
}

void find_pair(signed _N, vector<signed> U, vector<signed> V, signed A, signed B) {
      n = _N, a = A, b = B;

      assert(n < N);

      for (int i = 0; i + 1 < n; ++i)
            g[U[i]].pb({V[i], i}), g[V[i]].pb({U[i], i}), e.pb({U[i], V[i]});

      len = ask(vector<signed>(n - 1)) / a;

      int ans = solve_rooted(0, -1);
//      show(ans);
      assert(ans > 0);

      answer(0, ans); return;

      int l = 0, r = n - 2;

      int tt = 0;

      while (l < r) {
            int mid = (l + r) >> 1;

            vector<signed> v(n - 1);
            fill(v.begin() + l, v.begin() + mid + 1, 1);

//            for (int x : v)
//                  cerr << x;
//            cerr << '\n';

            if (query(v))
                  r = mid;
            else
                  l = mid + 1;
      }

      auto [x, y] = e[l];

//      show(x), show(y);

      vector<signed> check(n - 1);
      check[l] = true;

      assert(query(check));

      int res_x = solve_rooted(x, y);
      int res_y = solve_rooted(y, x);

      answer(res_x, res_y);
}

//6 5 1 2 0 5
//0 1
//0 4
//1 2
//1 3
//4 5

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:112:11: warning: unused variable 'tt' [-Wunused-variable]
  112 |       int tt = 0;
      |           ^~

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