Submission #600537

#	Time	Username	Problem	Language	Result	Execution time	Memory
600537		MilosMilutinovic	Highway Tolls (IOI18_highway)	C++14	0 / 100	17 ms	1396 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) {
  int m = (int) u.size();
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    g[u[i]].emplace_back(v[i], i);
    g[v[i]].emplace_back(u[i], i);
  }
  long long d = ask(vector<int>(m, 0));
  int low = 0, high = m - 1, id = -1;
  while (low <= high) {
    int mid = low + high >> 1;
    vector<int> qv(m);
    for (int i = 0; i <= mid; i++) {
      qv[i] = 1;
    }
    if (ask(qv) != d) {
      id = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  vector<int> ver(2);
  ver[0] = u[id];
  ver[1] = v[id];
  vector<vector<int>> dist(2, vector<int>(n, -1));
  for (int t = 0; t < 2; t++) {
    vector<int> que(1, ver[t]);
    dist[t][ver[t]] = 0;
    for (int b = 0; b < (int) que.size(); b++) {
      int i = que[b];
      for (auto &p : g[i]) {
        int j = p.first;
        if (dist[t][j] == -1) {
          dist[t][j] = dist[t][i] + 1;
          que.push_back(j);
        }
      }
    }
  }
  vector<int> ans(2);
  for (int t = 0; t < 2; t++) {
    vector<int> que(1, ver[t]);
    vector<int> dep(n, -1);
    dep[ver[t]] = 0;
    int cc = 0;
    vector<int> f(m);
    vector<int> edge(m, -1);
    for (int b = 0; b < (int) que.size(); b++) {
      int i = que[b];
      for (auto &p : g[i]) {
        int j = p.first;
        int idx = p.second;
        if (dist[t][j] >= dist[1 - t][j]) {
          continue;
        }
        if (dep[j] == -1) {
          dep[j] = dep[i] + 1;
          que.push_back(j);
          f[cc] = j;
          edge[idx] = cc++;
        } else if (dep[j] == dep[i] + 1) {
          edge[idx] = n;
        }
      }
    }
    int low = 0, high = cc - 1, at = -1;
    while (low <= high) {
      int mid = low + high >> 1;
      vector<int> qv(m);
      for (int i = 0; i < m; i++) {
        if (edge[i] == n || (edge[i] != -1 && edge[i] <= mid)) {
          qv[i] = 1;
        }
      }
      if (ask(qv) != d) {
        at = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    ans[t] = (at == -1 ? ver[t] : f[at]);
  }
  answer(ans[0], ans[1]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:16:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |     int mid = low + high >> 1;
      |               ~~~~^~~~~~
highway.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |       int mid = low + high >> 1;
      |                 ~~~~^~~~~~

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