Submission #836202

#	Time	Username	Problem	Language	Result	Execution time	Memory
836202		Johann	Highway Tolls (IOI18_highway)	C++14	51 / 100	193 ms	262144 KiB

highway

#include "highway.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, M;
vvpii adj;
vi par, depth;
std::vector<int> W;
ll shortest;
ll A, B;

void dfs(int v, int p)
{
  depth[v] = depth[p] + 1;
  for (pii e : adj[v])
    if (e.first != p)
      par[e.first] = e.second, dfs(e.first, v);
}

int findStuff(int v, int u, int eidx)
{
  par.assign(N, -1);
  depth.assign(N, 0);
  par[v] = eidx;
  dfs(v, u);
  W.assign(M, 0);
  for (int i = 0; i < N; ++i)
    if (par[i] != -1)
      W[par[i]] = 1;
  int d = (ask(W) - shortest) / (B - A);
  assert(d > 0);
  vi cand;
  for (int i = 0; i < N; ++i)
    if (depth[i] == d)
      cand.push_back(i);

  int base = 0;
  for (int j = 0; (1 << j) < sz(cand); ++j)
  {
    W.assign(M, 0);
    for (int i = 1; base + (i << j) < sz(cand); i += 2)
      W[par[cand[base + (i << j)]]] = 1;

    if (shortest < ask(W))
      base |= 1 << j;
  }
  return cand[base];
}

void find_pair(int _N, std::vector<int> U, std::vector<int> V, int _A, int _B)
{
  N = _N, M = U.size();
  A = _A, B = _B;
  adj = vvpii(N);
  for (int i = 0; i < M; ++i)
    adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i});

  W.assign(M, 0);
  shortest = ask(W);

  // find edge on shortest path
  int base = 0;
  for (int j = 0; (1 << j) < M; ++j)
  {
    W.assign(M, 0);
    for (int i = 1; (i << j) + base < M; i += 2)
      W[base + (i << j)] = 1;

    if (shortest < ask(W))
      base |= 1 << j;
  }

  // find distance of s and t to this edge
  int s = findStuff(U[base], V[base], base);
  int t = findStuff(V[base], U[base], base);

  answer(s, t);
}

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