Submission #587249

#	Time	Username	Problem	Language	Result	Execution time	Memory
587249		kamelfanger83	Highway Tolls (IOI18_highway)	C++14	0 / 100	22 ms	6088 KiB

highway

#include <iostream>
#include <vector>
#include "highway.h"

using namespace std;

vector<vector<pair<int, int>>> cons;
vector<int> 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(int N, vector<int> U, vector<int> V, int A, int 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<int> (M));
  auto qrange = [&](int l, int r){
    vector<int> w(M);
    for(int i = l; i < r; i++) w[i] = 1;
    return ask(w) != dst;
  };
  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<int>(M);
  dfs(U[l], V[l], 0, side1);
  w = vector<int>(M);
  dfs(V[l], U[l], 0, side2);
  int dst2 = (ask(w)-dst)/B;
  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<int> lw (M);
      for(int set = l; set < m; set++) lw[sel[set].second] = 1;
      if(ask(lw) != dst) r = m;
      else l = m;
    }
    return sel[l].first;
  };

  answer(bs_sel(side1[dst-dst2]), bs_sel(side2[dst2]));
}

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