Submission #1026956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026956		Malix	Highway Tolls (IOI18_highway)	C++14	12 / 100	1571 ms	262144 KiB

highway

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll MD=1e9+7;

void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
  int m = U.size();
  vi arr(m);
  REP(i,0,m)arr[i]=0;
  long long d=ask(arr)/A;
  vi p(n,0);
  vi val(n,-1);
  vector<vector<pi>> a(n);
  REP(i,0,m){
    a[U[i]].PB({V[i],i});
    a[V[i]].PB({U[i],i});
  }

  //bfs
  queue<int> pq;
  vi dist(n,-1);vi lf(n,1);
  pq.push(0);dist[0]=0;
  while(!pq.empty()){
    int k=pq.front();
    pq.pop();
    for(auto u:a[k]){
      if(p[k]==u.F)continue;
      lf[k]=0;
      dist[u.F]=dist[k]+1;
      p[u.F]=k;
      val[u.F]=u.S;
      pq.push(u.F);
    }
  }

  //find distance from bottom
  REP(i,0,n)if(p[i]==0)p[i]=i;
  vii parent(n,vi(log2(n)+3));
  REP(i,0,n)parent[i][0]=p[i];
  REP(j,1,log2(n)+2)REP(i,0,n)parent[i][j]=parent[parent[i][j-1]][j-1];
  
  vi bb;
  REP(i,1,n)if(lf[i]==1)bb.PB(i);
  int s=bb.size();
  int minv=dist[bb[0]],maxv=dist[bb[0]];
  REP(i,0,s){
    minv=min(minv,dist[bb[i]]);
    maxv=max(maxv,dist[bb[i]]);
  }
  int l=minv-maxv,r=n-1;
  while(l!=r){
    arr.clear();
    arr.resize(m,0);
    int mid=floor((l+r)/(double)2);
    REP(i,0,s){
      int e=mid+dist[bb[i]]-minv;
      if(e<0)continue;
      int q=bb[i];
      while(e>0){
        int f=LSOne(e);//cerr<<e<<" "<<f<<" "<<q<<"\n";
        q=parent[q][log2(f)];
        e-=f;
      }
      arr[val[q]]=1;
    }
      // for(auto u:arr)cerr<<u<<" ";
      // cerr<<"\n";
    if(ask(arr)>d*A)r=mid;
    else l=mid+1;
  }
  //find the node
  vi b;
  REP(i,0,s){
      int e=l+dist[bb[i]]-minv;
      if(e<0)continue;
      int q=bb[i];
      while(e>0){
        int f=LSOne(e);//cerr<<e<<" "<<f<<" "<<q<<"\n";
        q=parent[q][log2(f)];
        e-=f;
      }
      b.PB(q);
  }
  s=b.size();
  l=0,r=s-1;
  while(l!=r){
    arr.clear();
    arr.resize(m,0);
    int mid=(l+r)/2;
    REP(i,0,mid+1)arr[val[b[i]]]=1;
    if(ask(arr)>d*A)r=mid;
    else l=mid+1;
  }
  int ans1=b[l];

  //bfs again
  dist.clear();
  dist.resize(n,-1);
  pq.push(ans1);dist[ans1]=0;
  p.clear();
  p.resize(n,-1);
  val.clear();val.resize(n,-1);
  while(!pq.empty()){
    int k=pq.front();
    pq.pop();
    for(auto u:a[k]){
      if(p[k]==u.F)continue;
      dist[u.F]=dist[k]+1;
      p[u.F]=k;
      val[u.F]=u.S;
      pq.push(u.F);
    }
  }

  b.clear();
  REP(i,0,n)if(dist[i]==d)b.PB(i);
  s=b.size();
  l=0,r=s-1;
  while(l!=r){
    arr.clear();
    arr.resize(m,0);
    int mid=(l+r)/2;
    REP(i,0,mid+1)arr[val[b[i]]]=1;
    if(ask(arr)>d*A)r=mid;
    else l=mid+1;
  }
  // cerr<<ans1<<" "<<b[l];
  answer(ans1, b[l]);
}

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