Submission #441480

#	Time	Username	Problem	Language	Result	Execution time	Memory
441480		prvocislo	Highway Tolls (IOI18_highway)	C++17	100 / 100	361 ms	15060 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 9e4 + 5, maxm = 1.3e5 + 5;
vector<pair<int, int> > g[maxn]; // {index hrany, kam ide}
vector<int> t[maxn]; // hrany v bfs strome ale opacne
vector<int> mn[2]; // mnozina v ktorej moze byt s, mnozina v ktorej moze byt t
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
  int m = U.size();
  vector<int> w(m, 0);
  ll wa = ask(w);
  int lo = 0, hi = m-1;
  while (lo < hi)
  {
    int mi = (lo+hi)>>1;
    for (int i = 0; i < m; i++) w[i] = (i <= mi);
    if (ask(w) == wa) lo = mi+1; // Prvych mi hran nema ziaden vplyv na odpoved, id bude nejaka vyssia hrana.
    else hi = mi; 
  }
  int id = lo;
  for (int i = id; i < m; i++) g[U[i]].push_back({i, V[i]}), g[V[i]].push_back({i, U[i]});
  queue<int> q;
  vector<int> d(maxn, -1), x(maxn, 0);
  d[U[id]] = d[V[id]] = 0, x[U[id]] = 1, x[V[id]] = 2;
  q.push(U[id]), q.push(V[id]);
  while (!q.empty())
  {
    int u = q.front(); q.pop();
    if (x[u]&1) mn[0].push_back(u);
    if (x[u]&2) mn[1].push_back(u);
    for (pair<int, int> i : g[u])
    {
      if (d[i.second] == -1) d[i.second] = d[u] + 1, x[i.second] = x[u], q.push(i.second);
      if (d[i.second] == d[u] + 1) t[i.second].push_back(i.first);
    }
  }
  vector<int> ans(2, -1);
  for (int it = 0; it < 2; it++)
  {
    int lo = 0, hi = mn[it].size() - 1;
    while (lo < hi)
    {
      int mi = (lo+hi+1)>>1;
      w.assign(m, 0);
      for (int i = 0; i < id; i++) w[i] = 1;
      for (int i = mi; i < mn[it].size(); i++)
      {
        if (mn[it][i] == ans[0]) continue;
        for (int j : t[mn[it][i]]) w[j] = 1;
      }
      if (ask(w) == wa) hi = mi-1; // tieto vrcholy neovplivnili dlzku najkratsej cesty, treba ist nizsie
      else lo = mi;
    }
    ans[it] = mn[it][lo];
  }
  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:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |       for (int i = mi; i < mn[it].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~

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