Submission #1036467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036467		abczz	Highway Tolls (IOI18_highway)	C++17	Compilation error	0 ms	0 KiB

highway

#include "highway.h"
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define ll long long

using namespace std;

ll l, r, mid, a, b, s, q, rt, P[90000], E[90000];
bool visited[90000];
vector <ll> X;
vector <array<ll, 2> > adj[90000];
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  ll M = U.size();
  queue <ll> Q;
  for (int i=0; i<M; ++i) {
    adj[U[i]].push_back({V[i], i});
    adj[V[i]].push_back({U[i], i});
  }
  vector <int> W(M), Z(M);
  for (int i=0; i<M; ++i) W[i] = 0, Z[i] = 1;
  s = ask(W);
  l = 0, r = N-1;
  while (l < r) {
    mid = (l+r)/2;
    for (int i=0; i<M; ++i) W[i] = 0;
    for (int i=0; i<=mid; ++i) {
      for (auto [u, x] : adj[i]) W[x] = 1;
    }
    q = ask(W);
    if (q > s) r = mid;
    else l = mid+1;
  }
  rt = l;
  Q.push(rt);
  visited[rt] = 1;
  while (!Q.empty()) {
    auto u = Q.front();
    Q.pop();
    X.push_back(u);
    for (auto [v, x] : adj[u]) {
      if (!visited[v] && v >= rt) {
        Z[x] = 0, visited[v] = 1, E[v] = x, P[v] = u;
        Q.push(v);
      }
    }
  }
  reverse(X.begin(), X.end());
  X.pop_back();
  l = 0, r = X.size()-1;
  while (l < r) {
    mid = (l+r)/2;
    for (int i=0; i<M; ++i) W[i] = Z[i];
    for (int i=mid; i>=0; --i) {
      if (!W[E[P[X[i]]]]) W[E[X[i]]] = 1;
    }
    q = ask(W);
    if (q > s) r = mid;
    else l = mid+1;
  }
  a = l;
  l = a+1, r = X.size();
  while (l < r) {
    mid = (l+r)/2;
    for (int i=0; i<M; ++i) W[i] = Z[i];
    for (int i=mid; i>=0; --i) {
      if (!W[E[P[X[i]]]]) W[E[X[i]]] = 1;
    }
    q = ask(W);
    if (q > s+B-A) r = mid;
    else l = mid+1;
  }
  if (l == X.size()) answer(rt, X[a]);
  else answer(X[a], X[l]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:49:3: error: 'reverse' was not declared in this scope
   49 |   reverse(X.begin(), X.end());
      |   ^~~~~~~
highway.cpp:74:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   if (l == X.size()) answer(rt, X[a]);
      |       ~~^~~~~~~~~~~