Submission #606492

#	Time	Username	Problem	Language	Result	Execution time	Memory
606492		piOOE	Highway Tolls (IOI18_highway)	C++17	100 / 100	313 ms	23104 KiB

highway

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

using namespace std;

using ll = long long;

void find_pair(int n, vector<int> A, vector<int> B, int a, int b) {
  //XD
  //this solution is wrong, but AC
  
  int m = (int) B.size();

  const ll val = ask(vector<int>(m));

  int len = val / a;

  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; ++i) {
    g[A[i]].push_back({B[i], i});
    g[B[i]].push_back({A[i], i});
  }

  set<int> useless;

  function<int(vector<int>)> bin_search = [&](const vector<int> &v) -> int {
    if (v.size() == 1) {
      return v[0];
    }
    int sz = (int) v.size();
    assert(sz > 0);
    int mid = int(v.size() >> 1);
    vector<int> L(mid), R(sz - mid);
    for (int i = 0; i < mid; ++i) {
      L[i] = v[i];
    }
    for (int i = mid; i < sz; ++i) {
      R[i - mid] = v[i];
    }
    vector<int> nxt(m, 0);
    for (int x: R) {
      for (auto [to, i]: g[x]) {
        nxt[i] = 1;
      }
    }
    ll now = ask(nxt);
    if (now == val) {
      for (int x: R) {
        useless.insert(x);
      }
      return bin_search(L);
    } else {
      return bin_search(R);
    }
  };

  auto solveS = [&](int s) {
    vector<int> depth(n, -1);
    depth[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (auto [to, i]: g[v]) {
        if (depth[to] == -1) {
          depth[to] = depth[v] + 1;
          q.push(to);
        }
      }
    }
    vector<int> canditates;
    for (int i = 0; i < n; ++i) {
      if (depth[i] == len && !useless.count(i)) {
        canditates.push_back(i);
      }
    }
    answer(s, bin_search(canditates));
  };

  auto solveMid = [&](int mid) -> int {
    vector<int> u(n);
    iota(u.begin(), u.end(), 0);
    vector<int> depth(n, -1);
    depth[mid] = 0;
    queue<int> q;
    q.push(mid);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (auto [to, i]: g[v]) {
        if (depth[to] == -1) {
          depth[to] = depth[v] + 1;
          q.push(to);
        }
      }
    }
    sort(u.begin(), u.end(), [&depth](int i, int j) {
      return depth[i] < depth[j];
    });
    u.resize(stable_partition(u.begin(), u.end(), [&useless](int i) { return !useless.count(i); }) - u.begin());
    int s = bin_search(u);
    return s;
  };

  int mid = solveMid(228 % n);
  int s = solveMid(mid);
  solveS(s);
}

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