Submission #229646

#	Time	Username	Problem	Language	Result	Execution time	Memory
229646		MarcoMeijer	Highway Tolls (IOI18_highway)	C++14	100 / 100	286 ms	22016 KiB

highway

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

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define pb push_back
#define fi first
#define se second
#define sz size()

//===================//
//   begin program   //
//===================//

const int MX = 5e5;
int n, m, a, b, e;
vi w, u, v;
vii adj[MX];
ll dist;
vi onPath, visited;

int getS(vii& binU, vii& binV) {
  // binaray search for s
  int lb=0, ub=binU.sz-1;
  while(lb != ub) {
    int mid=(lb+ub+1)/2;
    RE(i,m) w[i] = 1;
    for(ii p:binV) w[p.se] = 0;
    RE(i,mid) w[binU[i].se] = 0;
    if(ask(w) == dist) ub = mid-1;
    else lb = mid;
  }
  return binU[lb].fi;
}

void find_pair(int N, vi U, vi V, int A, int B) {
  n=N; a=A; b=B; u=U; v=V;
  m = u.sz;
  RE(i,m) {
    adj[u[i]].pb({v[i], i});
    adj[v[i]].pb({u[i], i});
  }
  w.assign(m, 0);
  dist = ask(w);

  // get edge e on path s - t
  int lb=0, ub=m-1;
  while(lb != ub) {
    int mid=(lb+ub)/2;
    RE(i,m) w[i] = 1;
    RE(i,mid+1) w[i] = 0;
    if(ask(w) == dist) ub = mid;
    else lb = mid+1;
  }
  e = lb;

  // bfs
  visited.assign(n, 0);
  vii binU, binV;
  queue<pair<int, bool>> q;
  q.push({u[e],1}); visited[u[e]] = 1; binU.pb({u[e], e});
  q.push({v[e],0}); visited[v[e]] = 1; binV.pb({v[e], e});
  while(!q.empty()) {
    auto u = q.front(); q.pop();
    for(ii v : adj[u.fi]) {
      if(visited[v.fi]) continue;
      visited[v.fi] = 1;
      q.push({v.fi, u.se});
      if(u.se)  binU.pb(v);
      else      binV.pb(v);
    }
  }

  int s = getS(binU, binV);
  int t = getS(binV, binU);
  answer(s, t);
}

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