Submission #1026755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026755		Malix	Highway Tolls (IOI18_highway)	C++14	12 / 100	1107 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,-1);
  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});
  }
  queue<int> pq;
  vi dist(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;
      dist[u.F]=dist[k]+1;
      p[u.F]=k;
      val[u.F]=u.S;
      pq.push(u.F);
    }
  }
  vi b;
  REP(i,0,n)if(dist[i]==d)b.PB(i);
  int s=b.size();
  int 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;
  }
  answer(0, 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