Submission #299643

#	Time	Username	Problem	Language	Result	Execution time	Memory
299643		user202729	Highway Tolls (IOI18_highway)	C++17	100 / 100	261 ms	11556 KiB

highway

// moreflags=grader.cpp
// :(
#include "highway.h"
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<vector>
#include<cstdint>
#include<algorithm>

void find_pair(int number, std::vector<int> U, std::vector<int> V, int A, int B) {
	std::vector<int> query(U.size(), 0);
	auto const d1=ask(query); // a*(distance from S to T)

	int i=0;
	for(int step=1<<20; step>>=1;) if(i+step<(int)U.size()){
		query.assign(i+step, 1); query.resize(U.size(), 0);
		auto const d=ask(query);
		if(d==d1) i+=step;
	}
	// now i is the maximum value such that there's a shortest path not passing through the first i edges
	// therefore there must be a shortest path passing through edge [i]

	struct Edge{int node, index;};

	std::array<std::vector<Edge>, 2> edges; // edge indices in the bfs tree, split by sourceIndex,
	// each one is ordered by distance from source node
	// (node in each edge struct is the node farther from the corresponding source node)

	std::array<int, 2> source{{U[i], V[i]}};
	{
		// construct adjacency list
		std::vector<std::vector<Edge>> add(number);
		for(int index=0; index<(int)U.size(); ++index){
			auto const a=U[index], b=V[index];
			add[a].push_back({b, index}); add[b].push_back({a, index});
		}

		// multisource bfs from edge [i]
		struct Item{int node, sourceIndex;};
		std::vector<Item> queue; queue.reserve(number);
		std::vector<char> visited(number);
		for(int i=0; i<2; ++i){
			queue.push_back({source[i], i}); visited[source[i]]=true;
		}
		for(int start=0; start<(int)queue.size(); ++start){
			auto const [node, sourceIndex]=queue[start];
			for(auto [other, edgeIndex]: add[node]) if(not visited[other]){
				edges[sourceIndex].push_back({other, edgeIndex});
				visited[other]=true;
				queue.push_back({other, sourceIndex});
			}
		}
	}

	std::array<int, 2> result;
	for(int sourceIndex=0; sourceIndex<2; ++sourceIndex){
		int j=(int)edges[sourceIndex].size();
		for(int step=1<<20; step>>=1;) if(j-step>=0){
			query.assign(U.size(), 1);
			query[i]=0;
			for(auto [other, index]: edges[not sourceIndex]) query[index]=0;
			for(int k=0; k<j-step; ++k) query[edges[sourceIndex][k].index]=0;
			if(ask(query)==d1) j-=step;
		}
		// now j is the smallest value such that the sourceIndex half of the shortest path
		// is included in the first j nodes of edges[sourceIndex]
		result[sourceIndex]=j==0 ? source[sourceIndex]: edges[sourceIndex][j-1].node;
	}
	answer(result[0], result[1]);
}

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