Submission #1197160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197160		simplemind_31	통행료 (IOI18_highway)	C++20	18 / 100	278 ms	327680 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> dist;
vector<pair<int,int>> padre;
vector<int> vv,uu;
int n,m,dist111,dist222;
ll res,a,b;
void dfs(int now,int ante){
  for(auto u:grafo[now]){
    if(u.first==ante){
      continue;
    }
    padre[u.first].first=now;
    padre[u.first].second=u.second;
    dist[u.first]=dist[now]+1;
    dfs(u.first,now);
  }
}
int bs1(int xx,int ante){
  dist.assign(n,-1);
  padre.assign(n,{-1,-1});
  dist[xx]=0;
  padre[xx]={xx,-1};
  dfs(xx,ante);
  vector<int> nuesort,cop;
  for(int i=0;i<n;i++){
    if(dist[i]!=-1){
      nuesort.push_back(dist[i]);
    }
  }
  sort(ALL(nuesort));
  int nn=nuesort.size();
  cop.push_back(nuesort[0]);
  for(int i=1;i<nn;i++){
    if(cop.back()!=nuesort[i]){
      cop.push_back(nuesort[i]);
    }
  }
  nuesort=cop;
  nn=nuesort.size();
  int iz=0,de=nn-1,con=0,con1=0;
  while(iz<de){
    vector<int> aske(m,0);
    int mid=(iz+de+1)>>1;
    for(int i=0;i<n;i++){
      if(dist[i]==nuesort[mid]){
        aske[padre[i].second]=1;
      }
    }
    if(res==ask(aske)){
      de=mid-1;
    }else{
      iz=mid;
    }
  }
  dist111=nuesort[iz];
  if(nuesort[iz]==0){
    return xx;
  }
  vector<int> aske(m,0),second;
  for(int i=0;i<n;i++){
    if(dist[i]==nuesort[iz]){
      aske[padre[i].second]=1;
      con++;
    }
  }
  ll resnow=res-a+b;
  while(con>1){
    second=aske;
    con1=con;
    for(int i=0;i<m;i++){
      if(second[i] && con1>(con/2)){
        second[i]=0;
        con1--;
      }
    }
    if(ask(second)==resnow){
      aske=second;
      con=con1;
    }else{
      for(int i=0;i<m;i++){
        if(second[i]>0){
          aske[i]=0;
        }
      }
      con-=con1;
    }
  }
  for(int i=0;i<m;i++){
    if(aske[i]){
      if(padre[vv[i]].first==uu[i]){
        return vv[i];
      }else{
        return uu[i];
      }
    }
  }
}
int bs2(int xx,int ante){
  dist.assign(n,-1);
  padre.assign(n,{-1,-1});
  dist[xx]=0;
  padre[xx]={xx,-1};
  dfs(xx,ante);
  int con=0,con1=0;
  dist222=res/a-dist111-1;
  if(dist222==0){
    return xx;
  }
  vector<int> aske(m,0),second;
  for(int i=0;i<n;i++){
    if(dist[i]==dist222){
      aske[padre[i].second]=1;
      con++;
    }
  }
  ll resnow=res-a+b;
  while(con>1){
    second=aske;
    con1=con;
    for(int i=0;i<m;i++){
      if(second[i] && con1>(con/2)){
        second[i]=0;
        con1--;
      }
    }
    if(ask(second)==resnow){
      aske=second;
      con=con1;
    }else{
      for(int i=0;i<m;i++){
        if(second[i]>0){
          aske[i]=0;
        }
      }
      con-=con1;
    }
  }
  for(int i=0;i<m;i++){
    if(aske[i]){
      if(padre[vv[i]].first==uu[i]){
        return vv[i];
      }else{
        return uu[i];
      }
    }
  }
}
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.clear();
  grafo.resize(n);
  vv=V;
  uu=U;
  for(int i=0;i<m;i++){
    grafo[U[i]].push_back({V[i],i});
    grafo[V[i]].push_back({U[i],i});
  }
  vector<int> aske(m,0);
  res=ask(aske);
  int iz=0,de=m-1;
  while(iz<de){
    aske.assign(m,0);
    int mid=(iz+de)>>1;
    for(int i=iz;i<=mid;i++){
      aske[i]=1;
    }
    if(ask(aske)==res){
      iz=mid+1;
    }else{
      de=mid;
    }
  }
  int x=U[iz],y=V[iz];
  int i=bs1(x,y),j=bs2(y,x);
  answer(i,j);
}

Compilation message (stderr)

highway.cpp: In function 'int bs1(int, int)':
highway.cpp:102:1: warning: control reaches end of non-void function [-Wreturn-type]
  102 | }
      | ^
highway.cpp: In function 'int bs2(int, int)':
highway.cpp:152:1: warning: control reaches end of non-void function [-Wreturn-type]
  152 | }
      | ^

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