Submission #132884

#	Time	Username	Problem	Language	Result	Execution time	Memory
132884		KieranHorgan	Highway Tolls (IOI18_highway)	C++17	5 / 100	272 ms	9164 KiB

highway

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

int N, M, A, B;
vector<signed> U, V;

const int MAXN = 90000;
const int MAXM = 130000;

int queriesSoFar = 0;

int allLightCost;

vector<pair<int,int>> AdjList[90005];
bitset<MAXN> nodesToCheck;
vector<int> edgesToCheck;

long long checkNodes() {
	edgesToCheck.assign(M,0);
	for(int v = 0; v < N; v++) {
		if(!nodesToCheck[v])
			continue;
		for(auto p: AdjList[v])
			edgesToCheck[p.second]=1;
	}

	queriesSoFar++;
	return ask(edgesToCheck);
}

void find_pair(signed N_, vector<signed> U_, vector<signed> V_, signed A_, signed B_) {
	N=N_; U=U_;V=V_;A=A_;B=B_;
	M = U.size();

	edgesToCheck.assign(M, 0);

	srand(time(NULL));

	for(int e = 0; e < M; e++) {
		AdjList[U[e]].push_back({V[e],e});
		AdjList[V[e]].push_back({U[e],e});
	}

	allLightCost = checkNodes();

	//-----------Get Edge In Path-------------//
	vector<int> randomisedNodes(N);
	for(int i = 0; i < N; i++)
		randomisedNodes[i]=i;
	random_shuffle(randomisedNodes.begin(), randomisedNodes.end());

	int lo = 0;
	int hi = N;
	while(lo+1 < hi) {
		int mid = (lo+hi)/2;
		nodesToCheck.reset();
		for(int i = 0; i < mid; i++)
			nodesToCheck[randomisedNodes[i]]=1;
		long long cur = checkNodes();
		if(cur > allLightCost) hi = mid;
		else lo = mid;
	}
	int onPath = randomisedNodes[lo];
	//-----------Get Edge In Path-------------//


	//------------Get Nearer End--------------//
	vector<int> dist(N,N+10);
	dist[onPath] = 0;
	queue<pair<int,int>> q;
	q.push({onPath, 0});
	while(!q.empty()) {
		int u = q.front().first;
		int d = q.front().second;
		q.pop();

		for(auto p: AdjList[u]) {
			int v = p.first;
			if(dist[v] > d+1) {
				dist[v] = d+1;
				q.push({v,d+1});
			}
		}
	}

	int diff = allLightCost/A;
	lo = 0;
	hi = (diff/2)+1;
	while(lo+1 < hi) {
		int mid = (lo+hi)/2;
		nodesToCheck.reset();
		for(int i = 0; i < N; i++)
			if(dist[i] < mid)
				nodesToCheck[i] = 1;
		long long expected = allLightCost - (mid)*2*A + (mid)*2*B;
		long long act = checkNodes();
		if(expected == act) lo = mid;
		else hi = mid;
	}
	int distToNearest = lo;
	//------------Get Nearer End--------------//


	//------------Get Closer Node-------------//
	vector<int> possibilites;
	for(int i = 0; i < N; i++)
		if(dist[i] == distToNearest)
			possibilites.push_back(i);
	random_shuffle(possibilites.begin(), possibilites.end());
	lo = 0;
	hi = possibilites.size();
	while(lo+1 < hi) {
		int mid = (lo+hi)/2;
		nodesToCheck.reset();
		for(int i = 0; i < mid; i++)
			nodesToCheck[possibilites[i]]=1;
		long long cur = checkNodes();
		if(cur == allLightCost)
			lo = mid;
		else if(cur == allLightCost + (B-A) + (B-A) + (B-A))
			hi = mid;
		else if(cur == allLightCost + (B-A))
			hi = mid;
		else {
			if(distToNearest*2 == diff)
				hi = mid;
			else
				lo = mid;
		}
	}
	int S = possibilites[lo];
	//------------Get Closer Node-------------//


	//------------Get Further Node------------//
	possibilites.clear();
	int distToFurther = diff - distToNearest;
	for(int i = 0; i < N; i++)
		if(dist[i] == distToFurther && i != S)
			possibilites.push_back(i);
	random_shuffle(possibilites.begin(), possibilites.end());
	lo = 0;
	hi = possibilites.size();
	while(lo+1 < hi) {
		int mid = (lo+hi)/2;
		nodesToCheck.reset();
		for(int i = 0; i < mid; i++) 
			nodesToCheck[possibilites[i]]=1;
		long long cur = checkNodes();
		if(cur == allLightCost)
			lo = mid;
		else
			hi = mid;
	}
	int T = possibilites[lo];
	//------------Get Further Node------------//
	answer(S,T);
}

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