Submission #475138

#	Time	Username	Problem	Language	Result	Execution time	Memory
475138		cs71107	Highway Tolls (IOI18_highway)	C++14	100 / 100	326 ms	12492 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>
#define f first
#define s second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 2e5+10;

vector<vector<pii> > graph;

int upar[MAXN];
int ud[MAXN];
int uque[MAXN];

int vpar[MAXN];
int vd[MAXN];
int vque[MAXN];

int chk[MAXN];

int uver[MAXN];
int vver[MAXN];


void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  int M = U.size();

  vector<int> w(M,0);

  const ll shortest_path = ask(w);
  ll cur_path = 0;

  int idx = 0;

  for(int i=16;i>=0;i--){

    if((idx|(1<<i))>=M)continue;

    for(int j=0;j<(idx|(1<<i));j++){
      w[j] = 1;
    }
    for(int j=(idx|(1<<i));j<M;j++){
      w[j] = 0;
    }

    cur_path = ask(w);

    if(!(shortest_path^cur_path)){
      idx|=(1<<i);
    }
  }

  int u = U[idx];
  int v = V[idx];

  //cout<<idx<<"\n";
  //cout<<u<<" "<<v<<"\n";

  graph = vector<vector<pii> > (N);

  for(int i=0;i<M;i++){
    graph[U[i]].push_back(pii(V[i],i));
    graph[V[i]].push_back(pii(U[i],i));
  }

  fill(ud,ud+N,-1);
  fill(upar,upar+N,-1);
  fill(vd,vd+N,-1);
  fill(vpar,vpar+N,-1);

  int L = 0;
  int R = 0;

  int here,there;

  ud[u] = 0;
  uque[0] = u;

  while(L<=R){
    here = uque[L]; L++;
    
    for(int i=0;i<(int)graph[here].size();i++){
      there = graph[here][i].f;
      if(ud[there]!=-1)continue;
      ud[there] = ud[here]+1;
      upar[there] = graph[here][i].s;
      R++;
      uque[R] = there;
    }
  }

  //cout<<R<<"\n";
  assert(R==(N-1));

  vd[v] = 0;
  vque[0] = v;

  L = 0;
  R = 0;

  while(L<=R){
    here = vque[L]; L++;
    
    for(int i=0;i<(int)graph[here].size();i++){
      there = graph[here][i].f;
      if(vd[there]!=-1)continue;
      vd[there] = vd[here]+1;
      vpar[there] = graph[here][i].s;
      R++;
      vque[R] = there;
    }
  }

  assert(R==(N-1));

  chk[idx] = 1;

  int cntu = 0,cntv = 0;

  uver[0] = u;

  for(int i=1;i<N;i++){
    here = uque[i];
    if(ud[here]<vd[here]){
      chk[upar[here]] = 1;
      cntu++;
      uver[cntu] = here;
    }
  }

  vver[0] = v;

  for(int i=1;i<N;i++){
    here = vque[i];
    if(vd[here]<ud[here]){
      chk[vpar[here]] = 1;
      cntv++;
      vver[cntv] = here;
    }
  }
  
  /*
  for(int i=0;i<=cntu;i++){
    cout<<uver[i]<<" ";
  }
  cout<<"\n";

  for(int i=0;i<=cntv;i++){
    cout<<vver[i]<<" ";
  }
  cout<<"\n";*/

  for(int i=0;i<M;i++){
    w[i] = chk[i]^1;
  }

  /*
  cout<<"initial w\n";

  for(int i=0;i<M;i++){
    cout<<w[i]<<" ";
  }
  cout<<"\n";*/

  int idu = 0;

  for(int t=16;t>=0;t--){

    if((idu|(1<<t))>cntu)continue;

    for(int i=idu|(1<<t);i<=cntu;i++){
      here = uver[i];
      w[upar[here]] = 1;
    }

    cur_path = ask(w);

    if(cur_path^shortest_path){
      idu|=(1<<t);
    }

    for(int i=idu|(1<<t);i<=cntu;i++){
      here = uver[i];
      w[upar[here]] = 0;
    }
  }

  int idv = 0;

  for(int t=16;t>=0;t--){

    if((idv|(1<<t))>cntv)continue;

    for(int i=idv|(1<<t);i<=cntv;i++){
      here = vver[i];
      w[vpar[here]] = 1;
    }

    cur_path = ask(w);

    if(cur_path^shortest_path){
      idv|=(1<<t);
    }

    for(int i=idv|(1<<t);i<=cntv;i++){
      here = vver[i];
      w[vpar[here]] = 0;
    }
  }

  int anss = uver[idu];
  int anst = vver[idv];

  answer(anss,anst);

  return;
}

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