Submission #587299

#	Time	Username	Problem	Language	Result	Execution time	Memory
587299		jasmin	Highway Tolls (IOI18_highway)	C++14	51 / 100	145 ms	26224 KiB

highway

#include <iostream>
#include <vector>
#include "highway.h"
 
#define int long long
 
using namespace std;
 
vector<vector<pair<int, int>>> cons;
vector<signed> w;
 
void dfs(int i, int from, int d, vector<vector<pair<int, int>>>& put){
  for(pair<int, int> p : cons[i]){
    int c = p.first, m = p.second;
    if(c == from) continue;
    put[d+1].push_back({c, m});
    w[m] = 1;
    dfs(c, i, d+1, put);
  }
}
 
void find_pair(signed N, vector<signed> U, vector<signed> V, signed A, signed B) {
  int M = U.size();
  cons = vector<vector<pair<int, int>>> (N); 
  for(int m = 0; m < M; m++){
    cons[U[m]].push_back({V[m], m});
    cons[V[m]].push_back({U[m], m});
  }
 
  int dst = ask(vector<signed> (M))/(int)A;
  auto qrange = [&](int ll, int rl){
    vector<signed> wl(M);
    for(int i = ll; i < rl; i++) wl[i] = 1;
    return ask(wl) != dst*(int)A;
  };
 
  int l = 0, r = M;
  while(l + 1 < r){
    int m = l + (r-l)/2;
    if(qrange(l, m)) r = m;
    else l = m;
  }
 
  vector<vector<pair<int, int>>> side1 (N);
  vector<vector<pair<int, int>>> side2 (N);
  w = vector<signed>(M);
  dfs(U[l], V[l], 0, side1);
  w = vector<signed>(M);
  dfs(V[l], U[l], 0, side2);
  int dst2 = (ask(w)-dst*(int)A)/(int)(B-A);
 
  auto bs_sel = [&](vector<pair<int, int>> sel){
    int l = 0, r = sel.size();
    while(l + 1 < r){
      int m = l + (r-l)/2;
      vector<signed> lw (M);
      for(int set = l; set < m; set++) lw[sel[set].second] = 1;
      if(ask(lw) != dst*(int)A) r = m;
      else l = m;
    }
    return sel[l].first;
  };
 
  int u, s;
  if(dst2 > 0) u = bs_sel(side2[dst2]);
  else u = V[l];
  if(dst-dst2-1 > 0) s = bs_sel(side1[dst-dst2-1]);
  else s = U[l];
  answer(u, s);
}

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