Submission #222816

#	Time	Username	Problem	Language	Result	Execution time	Memory
222816		rama_pang	Highway Tolls (IOI18_highway)	C++14	100 / 100	222 ms	9292 KiB

highway

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

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  int M = U.size(), E = -1;

  lint base_cost_light = ask(vector<int>(M, 0));
  lint base_cost_heavy = (base_cost_light / A) * B;
    
  vector<int> heavy;
  vector<int> edge_list[2]; // edges that are in the BFS tree of U[E] and V[E]

  { // Binary Search to find an edge E which is in the shortest path from S to T if unweighted 
    heavy.assign(M, 0);
    int lo = 0, hi = M - 1;
    
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      for (int i = 0; i < M; i++) heavy[i] = i <= mid;
      if (ask(heavy) != base_cost_light) { // one of the heavy edges we set is in the unweighted shortest path
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }

    E = hi;
  }

  { // Create BFS Tree from both ends of E
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
      adj[U[i]].emplace_back(i);
      adj[V[i]].emplace_back(i);
    }

    vector<bool> vis(N, false);
    queue<pair<int, int>> q;
    vis[U[E]] = vis[V[E]] = true;
    q.emplace(U[E], 0), q.emplace(V[E], 1);

    while (!q.empty()) {
      int u = q.front().first;
      int t = q.front().second;
      q.pop();
      for (auto e_id : adj[u]) {
        int to = (U[e_id] ^ V[e_id] ^ u);
        if  (vis[to]) continue;
        vis[to] = true;
        q.emplace(to, t);
        edge_list[t].emplace_back(e_id);
        if (V[e_id] == u) swap(U[e_id], V[e_id]); // U is nearer than V
      }
    }
  }
  
  auto Get = [&](int root, vector<int> edges) { // Binary Search to find S and T
    // set all edges not in the BFS Tree to heavy traffic
    heavy.assign(M, 1);
    heavy[E] = 0;
    for (int i = 0; i < 2; i++) {
      for (auto j : edge_list[i]) {
        heavy[j] = 0;
      }
    }

    int lo = -1, hi = edges.size() - 1;

    while (lo < hi) {
      int mid = (lo + hi + 1) >> 1;
      for (int i = 0; i < (int) edges.size(); i++) heavy[edges[i]] = i >= mid;
      if (ask(heavy) != base_cost_light) { // there is a heavy edge from S to T
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }

    return hi == -1 ? root : V[edges[hi]]; // heavy edge in the BFS Tree
  };

  return answer(Get(U[E], edge_list[0]), Get(V[E], edge_list[1]));  
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:10:8: warning: unused variable 'base_cost_heavy' [-Wunused-variable]
   lint base_cost_heavy = (base_cost_light / A) * B;
        ^~~~~~~~~~~~~~~

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