Submission #282490

#	Time	Username	Problem	Language	Result	Execution time	Memory
282490		Haunted_Cpp	Highway Tolls (IOI18_highway)	C++17	51 / 100	177 ms	30072 KiB

highway

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

typedef long long i64;

const int MAX_N = 9e4 + 5;

vector<vector<pair<int, int>>> g(MAX_N);

vector<int> up(MAX_N);
vector<pair<int, int>> dist;
vector<vector<pair<int, int>>> h(MAX_N);

int Time = 0;
vector<int> in(MAX_N), out(MAX_N);

int _A, _B, max_h = 0;

void calc(int node, int p, int height, int where) {
  in[node] = ++Time;
  max_h = max(max_h, height);
  up[node] = where;
  h[height].emplace_back(up[node], node);
  for (auto to : g[node]) {
    if (to.first != p) {
      calc(to.first, node, height + 1, to.second);
    }
  }
  out[node] = Time;
}

int st;

bool in_sub(int u, int v) {
  return in[u] <= in[v] && out[u] >= out[v];
}

void dfs(int node, int p, i64 goal_distance, i64 w) {
  if (w == goal_distance) {
    if (in_sub(node, st) == false) {
      dist.emplace_back(up[node], node);
    } else {
      for (auto to : g[node]) {
        if (in[to.first] < in[node]) continue;
        if (in_sub(to.first, st) == true) {
          dist.emplace_back(to.second, node);
          break;
        }
      }
    }
  }
  for (auto to : g[node]) {
    if (to.first != p) {
      dfs(to.first, node, goal_distance, w + _A);
    }
  }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  _A = A;
  _B = B;
  const int m = (int) U.size();
  for (int i = 0; i < m; i++) {
    const int u = U[i];
    const int v = V[i];
    g[u].emplace_back(v, i);
    g[v].emplace_back(u, i);
  }
  calc(0, -1, 0, -1);
  vector<int> q(m);
  const i64 shortest_path = ask(q);
  int lo = 1, hi = max_h + 1;
  while(lo < hi) {
    const int mid = lo + (hi - lo) / 2;
    q.clear();
    q.resize(m);
    for (int i = max_h; i >= mid; i--) {
      for (auto to : h[i]) {
        q[to.first] = 1;
      }
    }
    i64 new_shortest = ask(q);
    if (new_shortest == shortest_path) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  --hi;
  const int lowest = hi;
  assert(hi > 0);
  lo = 0;
  hi = h[hi].size();
  while(lo < hi) {
    const int mid = lo + (hi - lo) / 2;
    q.clear();
    q.resize(m);
    for (int i = 0; i <= mid; i++) {
      q[h[lowest][i].first] = 1;
    }
    i64 new_shortest = ask(q);
    if (new_shortest > shortest_path) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  st = h[lowest][hi].second; 
  dfs(st, -1, shortest_path, 0);
  lo = 0;
  hi = (int) dist.size();
  while(lo < hi) {
    const int mid = lo + (hi - lo) / 2;
    q.clear();
    q.resize(m);
    for (int i = 0; i <= mid; i++) {
      const int edge = dist[i].first;
      q[edge] = 1;
    }
    i64 new_shortest = ask(q);
    if (new_shortest > shortest_path) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  answer(st, dist[hi].second);
}

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