Submission #587298

#	Time	Username	Problem	Language	Result	Execution time	Memory
587298		kamelfanger83	Highway Tolls (IOI18_highway)	C++14	11 / 100	167 ms	31820 KiB

highway

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

#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))/A;
  auto qrange = [&](int ll, int rl){
    vector<signed> wl(M);
    for(int i = ll; i < rl; i++) wl[i] = 1;
    int got = ask(wl);
    return ask(wl) != dst*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*A)/(B-A);

  auto bs_sel = [&](vector<pair<int, int>> sel){
    int l = -1, 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*A) r = m;
      else l = m;
    }
    assert(l >= 0);
    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);
}

/*
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <utility>

namespace {

constexpr int MAX_NUM_CALLS = 100;
constexpr long long INF = 1LL << 61;

int N, M, A, B, S, T;
std::vector<int> U, V;
std::vector<std::vector<std::pair<int, int>>> graph;

bool answered, wrong_pair;
int num_calls;

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

void wrong_answer(const char *MSG) {
  printf("Wrong Answer: %s\n", MSG);
  exit(0);
}

}  // namespace

long long ask(const std::vector<int> &w) {
  if (++num_calls > MAX_NUM_CALLS) {
    wrong_answer("more than 100 calls to ask");
  }
  if (w.size() != (size_t)M) {
    wrong_answer("w is invalid");
  }
  for (size_t i = 0; i < w.size(); ++i) {
    if (!(w[i] == 0 || w[i] == 1)) {
      wrong_answer("w is invalid");
    }
  }

  std::vector<bool> visited(N, false);
  std::vector<long long> current_dist(N, INF);
  std::queue<int> qa, qb;
  qa.push(S);
  current_dist[S] = 0;
  while (!qa.empty() || !qb.empty()) {
    int v;
    if (qb.empty() ||
        (!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
      v = qa.front();
      qa.pop();
    } else {
      v = qb.front();
      qb.pop();
    }
    if (visited[v]) {
      continue;
    }
    visited[v] = true;
    long long d = current_dist[v];
    if (v == T) {
      return d;
    }
    for (auto e : graph[v]) {
      int vv = e.first;
      int ei = e.second;
      if (!visited[vv]) {
        if (w[ei] == 0) {
          if (current_dist[vv] > d + A) {
            current_dist[vv] = d + A;
            qa.push(vv);
          }
        } else {
          if (current_dist[vv] > d + B) {
            current_dist[vv] = d + B;
            qb.push(vv);
          }
        }
      }
    }
  }
  return -1;
}

void answer(int s, int t) {
  if (answered) {
    wrong_answer("answered not exactly once");
  }

  if (!((s == S && t == T) || (s == T && t == S))) {
    wrong_pair = true;
  }

  answered = true;
}

int main() {
  N = read_int();
  M = read_int();
  A = read_int();
  B = read_int();
  S = read_int();
  T = read_int();
  U.resize(M);
  V.resize(M);
  graph.assign(N, std::vector<std::pair<int, int>>());
  for (int i = 0; i < M; ++i) {
    U[i] = read_int();
    V[i] = read_int();
    graph[U[i]].push_back({V[i], i});
    graph[V[i]].push_back({U[i], i});
  }

  answered = false;
  wrong_pair = false;
  num_calls = 0;
  find_pair(N, U, V, A, B);
  if (!answered) {
    wrong_answer("answered not exactly once");
  }
  if (wrong_pair) {
    wrong_answer("{s, t} is wrong");
  }
  printf("Accepted: %d\n", num_calls);
  return 0;
}
*/

Compilation message (stderr)

highway.cpp: In lambda function:
highway.cpp:35:9: warning: unused variable 'got' [-Wunused-variable]
   35 |     int got = ask(wl);
      |         ^~~

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