Submission #993672

#	Time	Username	Problem	Language	Result	Execution time	Memory
993672		poqmen	통행료 (IOI18_highway)	C++14	90 / 100	199 ms	9972 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>
using namespace std;
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
  vector<vector<int>> adj(n);
  int m = u.size();
  for (int i = 0; i < m; ++i)
    adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
  // ShortestPathDAG - {(u, v) | is_in_subgraph(u, v)} = Connected -> False
  // Disconnected -> True
  vector<int> hl(m, 0);
  int64_t req_d = ask(hl);
  auto is_shortestpathdag_cut =
      [&](function<bool(int, int)> is_in_cut) -> bool {
    for (int i = 0; i < m; ++i) {
      hl[i] = is_in_cut(u[i], v[i]);
    }
    return ask(hl) != req_d;
  };
  // find a cut in ShortestPathDAG w. smallest max element
  // i=il -> not cut, i=ih -> cut
  int il = 0, ih = n;
  while (il + 1 < ih) {
    int im = (il + ih) / 2;
    if (is_shortestpathdag_cut(
            [&](int u, int v) { return u < im || v < im; })) {
      ih = im;
    } else {
      il = im;
    }
  }
  // now remove all nodes < il
  // il is articulation point in ShortestPathDAG
  auto bfs = [&](int node) -> tuple<vector<int>, vector<int>> {
    vector<bool> visited(n, false);
    vector<int> bfs_ord;
    vector<int> in(n, INT_MAX);
    queue<int> q;
    q.push(node);
    visited[node] = true;
    int t = 0;
    while (!q.empty()) {
      auto top = q.front();
      q.pop();
      in[top] = t++;
      bfs_ord.push_back(top);
      for (auto v : adj[top]) {
        if (visited[v]) continue;
        if (v < il) continue;
        visited[v] = true;
        q.push(v);
      }
    }
    return {bfs_ord, in};
  };
  // ShortestPathDAG & BFSTree(il) has unique shortest path from s to t
  // node s and t are in different children of il
  auto find_end = [&](int root) {
    auto [bfs_ord, in] = bfs(root);
    // tl -> cut, th -> not cut
    int tl = 0, th = bfs_ord.size();
    while (tl + 1 < th) {
      int tm = (tl + th) / 2;
      if (is_shortestpathdag_cut([&](int u, int v) {
            if (u < il || v < il) return true;
            if (in[u] >= tm || in[v] >= tm) return true;
            return false;
          })) {
        tl = tm;
      } else {
        th = tm;
      }
    }
    // in tl, adding tl makes it uncut
    return bfs_ord[tl];
  };
  // tl -> cut, th -> not cut
  // graph @ tl + tl = th
  // tl = s
  int s = find_end(il);
  int t = find_end(s);
  answer(s, t);
}

#ifndef EVAL
#include "grader.cpp"
#endif

Compilation message (stderr)

highway.cpp: In lambda function:
highway.cpp:60:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     auto [bfs_ord, in] = bfs(root);
      |          ^

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