Submission #1037931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037931		Mr_Husanboy	Highway Tolls (IOI18_highway)	C++17	51 / 100	96 ms	16608 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()

template<typename T>
int len(T &a){
  return a.size();
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

vector<vector<int>> g;
vector<int> u, v;
int n, m;

vector<int> nodes, ch;

void dfs(int tar, int i, int p = -1, int d = 0){
  for(auto j : g[i]){
    int x = u[j] ^ v[j] ^ i;
    if(x == p) continue;
    if(d + 1 == tar){
      nodes.push_back(j);
      ch.push_back(x);
    }else{
      dfs(tar, x, i, d + 1);
    }
  }
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int a, int b) {
  n = N;
  u = U;
  v = V;
  m = len(v);
  g.resize(n);
  for(int i = 0; i < m; i ++){
    g[u[i]].push_back(i);
    g[v[i]].push_back(i);
  }
  vector<int> w(m, 1);
  ll d = ask(w) / b;
  queue<int> q;
  q.push(0);
  vector<int> vis(n);
  vector<int> ord;

  vis[0] = 1;
  while(!q.empty()){
    int t = q.front(); q.pop();
    for(auto j : g[t]){
      int x = u[j] ^ v[j] ^ t;
      if(vis[x]) continue;
      ord.push_back(j);
      ch.push_back(x);
      vis[x] = 1;
      q.push(x);
    }
  }
  int l = -2, r = n - 2;
  while(r - l > 1){
    int mid = (l + r) / 2;
    for(int j = 0; j <= mid; j ++){
      w[ord[j]] = 0;
    }
    for(int j = mid + 1; j < n - 1; j ++) w[ord[j]] = 1;
    if(d * a == ask(w)){
      r = mid;
    }else l = mid;
  }
  int s = (r == -1 ? 0 : ch[r]);
  ch.clear();
  dfs(d, s);
  l = -1, r = len(ch) - 1;
  w.assign(m, 1);
  while(r - l > 1){
    int mid = (l + r) / 2;
    for(int j = 0; j <= mid; j ++){
      w[nodes[j]] = 0;
    }
    for(int j = mid + 1; j < len(ch); j ++){
      w[nodes[j]] = 1;
    }
    if(ask(w) != d * b){
      r = mid;
    }else l = mid;

  }
  answer(s, ch[r]);
}

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