Submission #1216346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216346		not_amir	Highway Tolls (IOI18_highway)	C++20	23 / 100	121 ms	11572 KiB

highway

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

typedef pair<int, int> pii;

// constexpr pii E = {-1, -1};
//
// vector<vector<int>> G;
//
// vector<int> cmp;
// vector<bool> vis;
//
// int t = 0;
//
// void color(int v, int c, int &k, vector<int> &vec, vector<int> &rest) {
//   vis[v] = true;
//   vec.push_back(v);
//   cmp[v] = t, k--;
//   for (int u : G[v]) {
//     if (vis[u] || cmp[u] != c)
//       continue;
//     if (k)
//       color(u, c, k, vec, rest);
//     else
//       rest.push_back(u);
//   }
// }

vector<vector<pair<int, int>>> G;

vector<int> dist(int N, int v) {
  vector<bool> vis(N);
  vector<int> dist(N);
  queue<pii> q;
  q.push({v, 0});
  while (!q.empty()) {
    auto [v,d] = q.front();
    q.pop();
    if (vis[v])
      continue;
    vis[v] = true;
    dist[v] = d;
    for (auto [u, i] : G[v])
      if (!vis[u]) q.push({u, d + 1});
  }
  return dist;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  assert(U.size() == V.size());
  // int M = U.size();
  // G.resize(N);
  // cmp.resize(N);
  // for (int i = 0; i < M; i++)
  //   G[U[i]].push_back(V[i]), G[V[i]].push_back(U[i]);
  // vector<int> w(M);
  // int base = ask(w);
  // vector<vector<int>> r_cmp(2 * N);
  // r_cmp[0] = vector<int>(N);
  // iota(r_cmp[0].begin(), r_cmp[0].end(), 0);
  // vector<int> cut = {0}, search;
  // vector<pii> unite;
  // while (search.empty()) {
  //   vis.assign(N, 0);
  //   vector<int> nv;
  //   vector<int> n_cut;
  //   for (int c : cut) {
  //     int S = r_cmp[c].size();
  //     if (S == 1)
  //       continue;
  //     n_cut.push_back(++t);
  //     vector<int> rest, jnk;
  //     int k = S / 2;
  //     color(r_cmp[c][0], c, k, r_cmp[t], rest);
  //     for (int u : rest) {
  //       if (vis[u])
  //         continue;
  //       n_cut.push_back(++t);
  //       k = INT_MAX;
  //       color(u, c, k, r_cmp[t], jnk);
  //     }
  //   }
  //   for (int i = 0; i < M; i++)
  //     w[i] = cmp[U[i]] != cmp[V[i]];
  //   int res = ask(w);
  //   if (res != base)
  //     search = cut;
  //   else
  //     cut = n_cut;
  // }
  // int S = search.size();
  // vector<int> l(S), r(S), a(S), nxt(S, -1);
  // for (int i = 0; i < S; i++) {
  //   int c = search[i];
  //   l[i] = 0, r[i] = r_cmp[c].size();
  // }
  // while (true) {
  //   vis.assign(N, 0);
  //   cmp.assign(N, 0);
  //   auto tcmp = cmp;
  //   bool b = true;
  //   vector<int> e(S);
  //   for (int i = 0; i < S; i++) {
  //     if (l[i] > r[i] && nxt[i] == -1) {
  //       l[i] = 0, r[i] = r_cmp[search[i]].size();
  //       nxt[i] = a[i];
  //     }
  //     if (l[i] <= r[i]) {
  //       b = false;
  //       int m = (l[i] + r[i]) / 2;
  //       int c = search[i];
  //       vector<int> vec, jnk;
  //       color(r_cmp[c][0], c, m, vec, jnk);
  //       e[i] = vec.back();
  //     }
  //   }
  //   if (b)
  //     break;
  //   for (int i = 0; i < M; i++)
  //     w[i] = cmp[U[i]] != cmp[V[i]];
  //   cmp = tcmp;
  //   int res = ask(w);
  //   if (res == base) {
  //     for (int i = 0; i < S; i++) {
  //       if (l[i] <= r[i]) {
  //         int m = (l[i] + r[i]) / 2;
  //         l[i] = m + 1;
  //       }
  //     }
  //   }
  //   else {
  //     for (int i = 0; i < S; i++) {
  //       if (l[i] <= r[i]) {
  //         a[i] = e[i];
  //         int m = (l[i] + r[i]) / 2;
  //         r[i] = m - 1;
  //       }
  //     }
  //   }
  // }
  // int tl = 0, tr = S - 1;
  // int ans;
  // while (tl <= tr) {
  //   cmp.assign(N, 0);
  //   int m = (tl + tr) / 2;
  //   for (int i = 0; i <= m; i++)
  //     cmp[nxt[i]] = 1;
  //   for (int i = 0; i < M; i++)
  //     w[i] = cmp[U[i]] || cmp[V[i]];
  //   int res = ask(w);
  //   if (res != base)
  //     ans = m, tr = m -1;
  //   else
  //     tl = m + 1;
  // }
  // answer(a[ans], nxt[ans]);
  int M = U.size();
  G.resize(N);
  for (int i = 0; i < M; i++)
    G[U[i]].push_back({V[i], i}), G[V[i]].push_back({U[i], i});
  vector<int> w(M);
  int base = ask(w);
  int l = 0, r = M - 1, a;
  while (l <= r) {
    int m = (l + r) / 2;
    w = vector<int>(M);
    for (int i = 0; i < M; i++)
      w[i] = i < m;
    if (ask(w) == base)
      a = m, l = m + 1;
    else
      r = m - 1;
  }
  vector<int> p;
  array d = {dist(N, U[a]), dist(N, V[a])};
  for (int v : {U[a], V[a]}) {
    vector<int> ord;
    for (int i = 0; i < N; i++)
      if (d[0][i] < d[1][i])
        ord.push_back(i);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
      return d[0][i] > d[0][j];
    });
    int cur;
    l = 0, r = ord.size() - 1;
    while (l <= r) {
      int m = (l + r) / 2;
      w = vector<int>(M);
      for (int i = 0; i < a; i++)
        w[i] = 1;
      for (int i = 0; i < m; i++) {
        for (auto [u, idx] : G[ord[i]])
          w[idx] = 1;
      }
      if (ask(w) == base)
        l = m + 1, cur = ord[m];
      else
        r = m - 1;
    }
    swap(d[0], d[1]);
    p.push_back(cur);
  }
  answer(p[0], p[1]);
}

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