제출 #1199960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199960		simplemind_31	통행료 (IOI18_highway)	C++20	100 / 100	110 ms	12464 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
vector<vector<pair<int,int>>> grafo;
vector<int> dist1,dist2,aske,corres,indice,final;
vector<int> vv,uu;
int n,m,ahora;
ll res,a,b;
int bs2(){
  int iz=-1,de=ahora-1;
  while(iz<de){
    int mid=(iz+de+1)>>1;
    for(int i=0;i<m;i++){
      if(corres[i]>=mid){
        aske[i]=1;
      }else{
        aske[i]=0;
      }
    }
    if(ask(aske)!=res){
      iz=mid;
    }else{
      de=mid-1;
    }
  }
  return iz;
}
void find_pair(int N,vector<int> U,vector<int> V, int A, int B){
  a=A;b=B;n=N;
  m=U.size();
  grafo.resize(n);
  vv=V;uu=U;
  dist1.assign(n,-1);
  dist2=dist1;
  for(int i=0;i<m;i++){
    grafo[U[i]].push_back({V[i],i});
    grafo[V[i]].push_back({U[i],i});
  }
  aske.assign(m,0);
  res=ask(aske);
  int iz=0,de=m-1;
  while(iz<de){
    int mid=(iz+de)>>1;
    for(int i=0;i<m;i++){
      if(i<=mid){
        aske[i]=1;
      }else{
        aske[i]=0;
      }
    }
    if(ask(aske)==res){
      iz=mid+1;
    }else{
      de=mid;
    }
  }
  int x=U[iz],y=V[iz];
  dist1[x]=0;
  dist2[y]=0;
  queue<int> bfs;
  bfs.push(x);
  while(!bfs.empty()){
    int top=bfs.front();bfs.pop();
    for(auto u:grafo[top]){
      if(dist1[u.first]!=-1){
        continue;
      }
      dist1[u.first]=dist1[top]+1;
      bfs.push(u.first);
    }
  }
  bfs.push(y);
  while(!bfs.empty()){
    int top=bfs.front();bfs.pop();
    for(auto u:grafo[top]){
      if(dist2[u.first]!=-1){
        continue;
      }
      dist2[u.first]=dist2[top]+1;
      bfs.push(u.first);
    }
  }
  corres.assign(m,-1);
  indice.assign(n,0);
  final.assign(n,-1);
  final[x]=0;
  ahora=0;
  bfs.push(x);
  while(!bfs.empty()){
    int top=bfs.front();bfs.pop();
    for(auto u:grafo[top]){
      if(dist1[u.first]<dist2[u.first]){
        if(final[u.first]==-1){
          final[u.first]=final[top]+1;
          indice[ahora]=u.first;
          corres[u.second]=ahora++;
          bfs.push(u.first);
        }else if(final[u.first]==final[top]+1){
          corres[u.second]=n;
        }
      }else if(u.second!=iz){
        corres[u.second]=n;
      }
    }
  }
  int i=bs2();
  if(i==-1){
    i=x;
  }else{
    i=indice[i];
  }
  corres.assign(m,-1);
  indice.assign(n,0);
  final.assign(n,-1);
  final[y]=0;
  ahora=0;
  bfs.push(y);
  while(!bfs.empty()){
    int top=bfs.front();bfs.pop();
    for(auto u:grafo[top]){
      if(dist2[u.first]<dist1[u.first]){
        if(final[u.first]==-1){
          final[u.first]=final[top]+1;
          indice[ahora]=u.first;
          corres[u.second]=ahora++;
          bfs.push(u.first);
        }else if(final[u.first]==final[top]+1){
          corres[u.second]=n;
        }
      }else if(u.second!=iz){
        corres[u.second]=n;
      }
    }
  }
  int j=bs2();
  if(j==-1){
    j=y;
  }else{
    j=indice[j];
  }
  answer(i,j);
}

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