Submission #75245

#	Time	Username	Problem	Language	Result	Execution time	Memory
75245		Xellos	Highway Tolls (IOI18_highway)	C++14	100 / 100	664 ms	20328 KiB

highway

#include <bits/stdc++.h>
#define ff first
#define ss second
#include "highway.h"
using namespace std;

using cat = long long;

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  int M = U.size();
  vector<int> vq(M, 1);
  cat L = ask(vq) / B;
  // find edge on shortest path
  int el = 0, er = M;
  while(er - el > 1) {
  	int em = (el + er + 1) / 2;
  	for(int i = 0; i < em; i++) vq[i] = 0;
  	for(int i = em; i < M; i++) vq[i] = 1;
  	cat ans = ask(vq);
  	if(ans == L * A) er = em;
  	else el = em;
  }
  vector< vector< pair<int, int> > > G(N);
  for(int i = 0; i <= el; i++) {
  	G[U[i]].push_back({V[i], i});
  	G[V[i]].push_back({U[i], i});
  }
  // BFS graph for 2
  queue<int> q;
  vector<int> dep2(N, -1), v2;
  vector< vector<int> > e2_in(N);
  q.push(U[el]);
  dep2[U[el]] = 0;
  while(!q.empty()) {
  	v2.push_back(q.front());
  	for(auto e: G[q.front()]) if(dep2[e.ff] == -1) {
  		dep2[e.ff] = dep2[q.front()]+1;
  		q.push(e.ff);
  	}
  	q.pop();
  }
  for(int i = 0; i <= el; i++) {
  	if(dep2[U[i]] > dep2[V[i]]) e2_in[U[i]].push_back(i);
  	if(dep2[U[i]] < dep2[V[i]]) e2_in[V[i]].push_back(i);
  }
  int v2l = 0, v2r = v2.size();
  while(dep2[v2[v2r-1]] > L) v2r--;
  while(v2r-v2l > 1) {
  	int v2m = (v2l + v2r + 1) / 2;
  	for(int i = 0; i < M; i++) vq[i] = 1;
  	for(int i = 0; i < v2m; i++)
  		for(auto e: e2_in[v2[i]]) vq[e] = 0;
  	cat ans = ask(vq);
  	if(ans == L * A) v2r = v2m;
  	else v2l = v2m;
  }
  int S = v2[v2l];
  vector<bool> bl(N, false);
  vector<int> e_bl;
  int cur = S;
  while(dep2[cur] > 0) {
	bl[cur] = true;
  	for(auto e: G[cur]) if(dep2[e.ff] == dep2[cur]-1) {
  		e_bl.push_back(e.ss);
  		cur = e.ff;
  		break;
  	}
  }
  // BFS graph for 1
  vector<int> dep1(N, -1), v1;
  vector< vector<int> > e1_in(N);
  q.push(U[el]);
  dep1[U[el]] = 0;
  while(!q.empty()) {
  	v1.push_back(q.front());
  	for(auto e: G[q.front()]) if(!bl[e.ff] && dep1[e.ff] == -1) {
  		dep1[e.ff] = dep1[q.front()]+1;
  		q.push(e.ff);
  	}
  	q.pop();
  }
  for(int i = 0; i <= el; i++) if(!bl[U[i]] && !bl[V[i]]) {
  	if(dep1[U[i]] > dep1[V[i]]) e1_in[U[i]].push_back(i);
  	if(dep1[U[i]] < dep1[V[i]]) e1_in[V[i]].push_back(i);
  }
  int v1l = 0, v1r = v1.size();
  while(dep1[v1[v1r-1]] > L-dep2[S]) v1r--;
  while(v1r-v1l > 1) {
  	int v1m = (v1l + v1r + 1) / 2;
  	for(int i = 0; i < M; i++) vq[i] = 1;
  	for(auto e: e_bl) vq[e] = 0;
  	for(int i = 0; i < v1m; i++)
  		for(auto e: e1_in[v1[i]]) vq[e] = 0;
  	cat ans = ask(vq);
  	if(ans == L * A) v1r = v1m;
  	else v1l = v1m;
  }
  int T = v1[v1l];
  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