Submission #1237385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237385		noyancanturk	Highway Tolls (IOI18_highway)	C++20	100 / 100	146 ms	27044 KiB

highway

#include "highway.h"

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
  #define resetw w=vector<int>(m)

using pii=pair<int,int>;

const int lim=2e5;

int to[lim];
vector<int>v[lim],w;

int n,m,a,b;

pair<vector<int>,vector<vector<int>>>bfs(int st){
  vector<int>dist(n,INT_MAX);
  vector<vector<int>>pars(n);
  queue<int>q;
  dist[st]=0;
  q.push(st);
  while(q.size()){
    int node=q.front();
    q.pop();
    for(int id:v[node]){
      int j=to[id]^node;
      if(w[id]){
        continue;
      }
      if(dist[j]==INT_MAX){
        q.push(j);
        dist[j]=dist[node]+1;
      }
      if(dist[j]==dist[node]+1){
        pars[j].pb(id);
      }
    }
  }
  return {dist,pars};
}

void find_pair(int N,vector<int>U,vector<int>V,int A,int B){
  n=N;
  m=V.size();
  a=A;
  b=B;
  for(int i=0;i<m;i++){
    v[U[i]].pb(i);
    v[V[i]].pb(i);
    to[i]=U[i]^V[i];
  }
  resetw;
  int64_t none=ask(w);
  int l=0,r=m-2,res=m-1;
  while(l<=r){
    int mid=l+r>>1;
    resetw;
    for(int i=0;i<=mid;i++){
      w[i]=1;
    }
    int64_t cur=ask(w);
    if(cur==none){
      l=mid+1;
    }else{
      res=mid;
      r=mid-1;
    }
  }
  int guy=res;
  int x=U[guy],y=V[guy];
  vector<int>g1,g2;
  resetw;
  for(int i=0;i<=guy;i++){
    w[i]=1;
  }
  auto[d1,p1]=bfs(x);
  auto[d2,p2]=bfs(y);
  for(int i=0;i<n;i++){
    if(d1[i]<d2[i]){
      g1.pb(i);
    }else if(d2[i]<d1[i]){
      g2.pb(i);
    }
  }
  sort(g1.begin(),g1.end(),[&](int i,int j)-> bool {
    return d1[j]<d1[i];
  });
  sort(g2.begin(),g2.end(),[&](int i,int j)-> bool {
    return d2[j]<d2[i];
  });
  l=0,r=int(g1.size())-2,res=g1.size()-1;
  while(l<=r){
    int mid=l+r>>1;
    resetw;
    for(int i=0;i<guy;i++){
      w[i]=1;
    }
    for(int i=0;i<=mid;i++){
      for(int id:p1[g1[i]]){
        w[id]=1;
      }
    }
    int64_t cur=ask(w);
    if(cur==none){
      l=mid+1;
    }else{
      r=mid-1;
      res=mid;
    }
  }
  x=g1[res];
  l=0,r=int(g2.size())-2,res=g2.size()-1;
  while(l<=r){
    int mid=l+r>>1;
    resetw;
    for(int i=0;i<guy;i++){
      w[i]=1;
    }
    for(int i=0;i<=mid;i++){
      for(int id:p2[g2[i]]){
        w[id]=1;
      }
    }
    int64_t cur=ask(w);
    if(cur==none){
      l=mid+1;
    }else{
      r=mid-1;
      res=mid;
    }
  }
  y=g2[res];
  answer(x,y);
}

// void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
//   int M = U.size();
//   for (int j = 0; j < 50; ++j) {
//     std::vector<int> w(M);
//     for (int i = 0; i < M; ++i) {
//       w[i] = 0;
//     }
//     long long toll = ask(w);
//   }
//   answer(0, N - 1);
// }

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