Submission #1244900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244900		2288	Highway Tolls (IOI18_highway)	C++20	51 / 100	81 ms	11244 KiB

highway

#include "highway.h"

using namespace std;

#define ALL(x) begin(x),end(x)
#define pb push_back
#define F first
#define S second
// #define int long long

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vb> vvb;

template<typename T>
T meq(T& a, T b){
  return a=max(a,b);
}

void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
  int m = U.size();
  vvii g(n);
  for (int i=0;i<m;i++){
    g[U[i]].pb({V[i],i});
    g[V[i]].pb({U[i],i});
  }
  vi w(m, 0);
  ll dist = ask(w);

  vi dep(n,-1);
  vi depe(m,-1);
  vi pare(n,-1);
  auto dfs1 = [&](auto&& self, int i, int d) -> void {
    if (dep[i]!=-1)return;
    dep[i] = d;
    for (auto [j,eg]:g[i]){
      if (dep[j]!=-1)continue;;
      depe[eg]=d+1;
      pare[j]=eg;
      self(self, j, d+1);
    }
  };
  dfs1(dfs1, 0, 0);
  int dl=0,dr=0;
  for (int d:dep)meq(dr, d+1);
  while (dl<dr-1){
    int md=(dl+dr)/2;
    for (int i=0;i<m;i++)w[i]=depe[i]>=md;
    if (ask(w)>dist)dl=md;
    else dr=md;
  }
  vii poss;
  for (int i=0;i<n;i++){
    if (dep[i]==dl)poss.pb({i,pare[i]});
  }
  while (poss.size()>1){
    vii test;
    fill(ALL(w),0);
    while (test.size()<poss.size()){
      test.pb(poss.back());
      w[poss.back().S]=1;
      poss.pop_back();
    }
    if (ask(w)>dist){
      swap(test,poss);
    }
  }
  const int ans1 = poss[0].F;

  fill(ALL(dep),-1);
  vii poss2;
  auto dfs2 = [&](auto&& self, int i, int d) -> void {
    if (dep[i]!=-1)return;
    dep[i] = d;
    for (auto [j,eg]:g[i]){
      if (dep[j]!=-1)continue;
      if (d+1==dist/A){
        poss2.pb({j,eg});
      }
      self(self, j, d+1);
    }
  };
  dfs2(dfs2, ans1, 0);


  while (poss2.size()>1){
    vii test;
    fill(ALL(w),0);
    while (test.size()<poss2.size()){
      test.pb(poss2.back());
      w[poss2.back().S]=1;
      poss2.pop_back();
    }
    if (ask(w)>dist){
      swap(test,poss2);
    }
  }

  const int ans2 = poss2[0].F;
  
  answer(ans1, ans2);
}

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