Submission #1111973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111973		SalihSahin	Highway Tolls (IOI18_highway)	C++14	51 / 100	121 ms	17752 KiB

highway

#include <bits/stdc++.h>
#define pb push_back
//#define int long long
using namespace std;
#include "highway.h"

vector<vector<pair<int, int> > > adj;
vector<vector<int> > depth;
vector<int> d, topar, p;
int mxdep;

void dfs(int node, int par){
  if(node != par) d[node] = d[par] + 1;
  p[node] = par;
  mxdep = max(mxdep, d[node]);
  depth[d[node]].pb(node);

  for(auto itr: adj[node]){
    if(itr.first == par) continue;
    topar[itr.first] = itr.second;
    dfs(itr.first, node);
  }
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  int M = U.size();
  adj.resize(N);
  d.resize(N);
  depth.resize(N);
  topar.resize(N);
  p.resize(N);
  mxdep = 0;

  for(int i = 0; i < M; i++){
    adj[U[i]].pb({V[i], i});
    adj[V[i]].pb({U[i], i});
  }
  dfs(0, 0);

  vector<int> w(M, 0);
  long long dis = ask(w); // QUERY
  long long ec = dis / A;

  int l = 1, r = mxdep;
  while(l < r){
    int m = (l + r + 1)/2;

    for(int i = 0; i < M; i++) w[i] = 0;
    for(int i = m; i <= mxdep; i++){
      for(auto itr: depth[i]){
        w[topar[itr]] = 1;
      }
    }

    long long check = ask(w);
    if(check == dis) r = m - 1;
    else l = m; 
  }                            // LOG N QUERY

  for(int i = 0; i < M; i++) w[i] = 0;
  for(int i = l; i <= mxdep; i++){
    for(auto itr: depth[i]){
      w[topar[itr]] = 1;
    }
  }

  long long val = ask(w); // QUERY
  bool samedep = 0;
  if(val - dis > (B - A)) samedep = 1;
  int dep2 = l;

  if(samedep){
    vector<int> ans, vis(N);

    for(int dene = 0; dene < 2; dene++){
      vector<int> bsat;
      for(auto itr: depth[dep2]){
        if(!vis[itr]){
          bsat.pb(itr);
        }
      }

      l = 0, r = bsat.size()-1;
      while(l < r){
          int m = (l + r)/2;

          for(int i = 0; i < M; i++) w[i] = 0;
          for(int i = l; i <= m; i++){
            w[topar[bsat[i]]] = 1;
          }

          long long check = ask(w);
          if(check > dis) r = m;
          else l = m + 1;
      }                                 // LOG N QUERY

      ans.pb(bsat[l]);
      vis[bsat[l]] = 1;
    }

    answer(ans[0], ans[1]);
  }
  else{
    int ans2;
    l = 0, r = depth[dep2].size()-1;
    while(l < r){
      int m = (l + r)/2;

      for(int i = 0; i < M; i++) w[i] = 0;
      for(int i = l; i <= m; i++){
        w[topar[depth[dep2][i]]] = 1;
      }
      long long check = ask(w);
      if(check > dis) r = m;
      else l = m + 1;
    }                             // LOG N QUERY
    ans2 = depth[dep2][l];

    vector<int> vis(N);

    bool lcais1 = 0;
    int x = ans2;
    for(int i = 0; i < M; i++) w[i] = 0;
    while(x != 0){
      vis[x] = 1;
      w[topar[x]] = 1;
      x = p[x];
    }
    long long lcacheck = ask(w); // QUERY
    int lcadep;
    if(lcacheck == ec * B) lcais1 = 1;
    else{
      int side2ec = (lcacheck - dis) / (B - A);
      lcadep = dep2 - side2ec;
    }

    if(lcais1){
      int ans1 = ans2;
      for(int i = 0; i < ec; i++) ans1 = p[ans1];
      answer(ans1, ans2);
    }
    else{
      // ec == (dep2 - lcadep) + (dep1 - lcadep) -> ec == dep1 + dep2 - 2*lcadep
      int dep1 = ec - dep2 + 2*lcadep;

      vector<int> bsat;
      for(auto itr: depth[dep1]){
        if(!vis[itr]) bsat.pb(itr);
      }

      l = 0, r = bsat.size()-1;
      while(l < r){
        int m = (l + r)/2;

        for(int i = 0; i < M; i++) w[i] = 0;
        for(int i = l; i <= m; i++){
          w[topar[bsat[i]]] = 1;
        }

        long long check = ask(w);
        if(check > dis) r = m;
        else l = m + 1;
      }                                 // LOG N QUERY

      int ans1 = bsat[l];
      answer(ans1, ans2);
    }
  }
  //answer(0, N - 1); cevabı koy buraya
}

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