제출 #600540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600540		MilosMilutinovic	통행료 (IOI18_highway)	C++14	100 / 100	251 ms	11992 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, 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]) {
          if (dep[j] == -1) {
            dep[j] = dep[i] + 1;
            que.push_back(j);
            f.push_back(j);
            edge[idx] = cc++;
          } else if (dep[j] == dep[i] + 1) {
            edge[idx] = n;
          }
        } else {
          edge[idx] = (idx == id ? -1 : n);
        }
      }
    }
    reverse(f.begin(), f.end());
    for (int i = 0; i < m; i++) {
      if (edge[i] != -1 && edge[i] != n) {
        edge[i] = cc - edge[i] - 1;
      }
    }
    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]);
}

컴파일 시 표준 에러 (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:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |       int mid = low + high >> 1;
      |                 ~~~~^~~~~~

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