Submission #1037900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037900		Mr_Husanboy	Highway Tolls (IOI18_highway)	C++17	12 / 100	65 ms	8804 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);
  ll d = ask(w) / a;
  dfs(d, 0);
  int l = -1, r = len(nodes) - 1;
  //cout << r << endl;
  //for(auto u : ch) cout << u << endl;
  while(r - l > 1){
    int mid = (l + r) / 2;
    for(int i = 0; i <= mid; i ++){
      w[nodes[i]] = 1;
    }
    for(int i = mid + 1; i < len(nodes); i ++){
      w[nodes[i]] = 0;
    }
    if(ask(w) != d * a){
      r = mid;
    }else l = mid;
  }
  //cout << r << endl;
  answer(0, ch[r]);
}

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