Submission #594327

#	Time	Username	Problem	Language	Result	Execution time	Memory
594327		Soumya1	Highway Tolls (IOI18_highway)	C++17	100 / 100	248 ms	11764 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
const int mxN = 9e4 + 5;
vector<pair<int, int>> ad[mxN];
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
  int m = U.size();
  for (int i = 0; i < m; i++) {
    ad[U[i]].push_back({i, V[i]});
    ad[V[i]].push_back({i, U[i]});
  }
  int lo = 0, hi = m - 1;
  int len = ask(vector<int> (m)) / A;
  while (lo < hi) {
    int mid = (lo + hi) >> 1;
    vector<int> v(U.size(), 1);
    for (int i = 0; i <= mid; i++) {
      v[i] = 0;
    }
    if (ask(v) == 1LL * A * len) hi = mid;
    else lo = mid + 1;
  }
  int s = U[lo], e = V[lo];
  vector<int> d(n, -1), root(n);
  root[s] = s, root[e] = e;
  queue<int> q;
  vector<int> S, E, par(n);
  par[s] = par[e] = lo;
  S.push_back(s);
  E.push_back(e);
  q.push(s);
  q.push(e);
  d[s] = d[e] = lo;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto [i, v] : ad[u]) {
      if (d[v] == -1) {
        d[v] = d[u] + 1;
        q.push(v);
        root[v] = root[u];
        if (root[v] == s) {
          S.push_back(v);
          par[v] = i;
        } else {
          E.push_back(v);
          par[v] = i;
        }
      }
    }
  }
  auto get = [&](vector<int> ss, vector<int> ee) {
    lo = 0, hi = ss.size() - 1;
    while (lo < hi) {
      int mid = (lo + hi) >> 1;
      vector<int> v(m, 1);
      for (int i = 0; i < ee.size(); i++) v[par[ee[i]]] = 0;
      for (int i = 0; i <= mid; i++) {
        v[par[ss[i]]] = 0;
      }
      if (ask(v) == 1LL * len * A) hi = mid;
      else lo = mid + 1;
    }
    return ss[lo];
  };
  answer(get(S, E), get(E, S));
}

Compilation message (stderr)

highway.cpp: In lambda function:
highway.cpp:60:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |       for (int i = 0; i < ee.size(); i++) v[par[ee[i]]] = 0;
      |                       ~~^~~~~~~~~~~

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