Submission #592795

#	Time	Username	Problem	Language	Result	Execution time	Memory
592795		farhan132	Highway Tolls (IOI18_highway)	C++17	12 / 100	184 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back

const ll N = 1e5 + 5;

vector < ii > v[N];
ii edge[N]; ll in[N]; ll par[N];
ll n, m;
vector < ll > all;

void dfs(ll s, ll p){
  par[s] = p;
  for(auto [u, i] : v[s]){
    if(u - p){
      dfs(u, s);
      in[i] = all.size();
      all.pb(i);
      edge[i] = {s, u};
    }
  }
  return;
}
ll query(ll l, ll r){
  vector < int > w(m, 0);
  if(r == -1) return ask(w);
  for(ll i = l; i <= r; i++) w[all[i]] = 1;
  return ask(w);
}
vector < ll > collect;
void DFS(ll s, ll p){
  for(auto [u, i] : v[s]){
    if(u - p){
      DFS(u, s);
      collect.pb(i);
    }
  }
  return;
}

void find_pair(int _n, std::vector<int> U, std::vector<int> V, int A, int B) {
  n = _n, m = U.size();
  for(ll i = 0; i < m; i++){
    ll x = V[i], y = U[i];
    v[x].pb({y, i});
    v[y].pb({x, i});
  }
  dfs(0, -1);
  ll cost = query(0, -1);
  ll lo = 0, hg = m - 1;
  ll X = 0, root = 0, Y = 0;
  while(lo <= hg){
    ll mid = (lo + hg)/2;
    ll k = query(0, mid);
    if(k == cost){
      lo = mid + 1;
    }else{
      X = mid;
      hg = mid - 1;
    }
  }
  lo = 0, hg = m - 1;

  while(lo <= hg){
    ll mid = (lo + hg)/2;
    ll k = query(mid, m-1);

    if(k == cost){
       hg = mid - 1;
    }else{

      root = mid;
      lo = mid + 1;
    }
  }
  //return;
  ll _X = edge[all[X]].ss;
  ll _R = edge[all[root]].ff;
  DFS(edge[all[root]].ss, _R);
  collect.pb(root);
  sort(collect.begin(), collect.end());
  ll L = collect[0], R = collect.back();
  lo = L, hg = R;
  while(lo <= hg){
    ll mid = (lo + hg)/2;
    ll k = query(L, mid);
    if(k == cost){
      lo = mid + 1;
    }else{
      hg = mid - 1;
      Y = mid;
    }
  }


  ll _Y = edge[all[Y]].ss;
  int S,T;
  if(_X == _Y) S = _X, T = _R;
  else S = _X, T = _Y;
 // cout << _X << ' ' << _R << ' ' << _Y << '\n';
  answer(S, T);
  return;
}

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