Submission #282449

#	Time	Username	Problem	Language	Result	Execution time	Memory
282449		Haunted_Cpp	Highway Tolls (IOI18_highway)	C++17	12 / 100	303 ms	262148 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;

int _A, _B;

void calc(int node, int p, int where) {
  up[node] = where;
  for (auto to : g[node]) {
    if (to.first != p) {
      calc(to.first, node, to.second);
    }
  }
}

void dfs(int node, int p, i64 goal_distance, i64 w) {
  if (w == goal_distance) {
    dist.emplace_back(up[node], node);
  }
  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 st = 0;
  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, -1);
  vector<int> q(m);
  const i64 shortest_path = ask(q);
  dfs(0, -1, shortest_path, 0);
  // Assuming one node is 0
  int 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: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31