Submission #768225

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
768225	2023-06-27T17:43:53 Z	coloboxx	Highway Tolls (IOI18_highway)	C++17	6 / 100	92 ms	23536 KB

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'
#define int ll

using namespace std;

const int N = 1 << 18;

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

int norm(int 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);

//      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;
//      show(b - a);

      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 l = 0, r = n - 2;

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

            vector<signed> v(n - 1);
            for (int i = l; i <= mid; ++i)
                  v[i] = true;

            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

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	6352 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6480 KB	Output is correct
2	Incorrect	13 ms	7416 KB	Output is incorrect: {s, t} is wrong.
3	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	8188 KB	Output is correct
2	Correct	22 ms	10032 KB	Output is correct
3	Correct	28 ms	11792 KB	Output is correct
4	Correct	76 ms	20804 KB	Output is correct
5	Correct	62 ms	20812 KB	Output is correct
6	Correct	87 ms	22256 KB	Output is correct
7	Correct	89 ms	23536 KB	Output is correct
8	Correct	62 ms	21540 KB	Output is correct
9	Correct	92 ms	21872 KB	Output is correct