Submission #248394

#	Time	Username	Problem	Language	Result	Execution time	Memory
248394		user202729	Highway Tolls (IOI18_highway)	C++17	51 / 100	182 ms	9580 KiB

highway

// moreflags=grader.cpp
// :( (why did I implement the centroid before trying to figure out an easier solution...
// and that's just for the tree subtask.)


#include "highway.h"
#include<cassert>
#include<vector>
#include<cstdint>
#include<algorithm>

struct Solve{
	struct Edge{
		int node, index;
	};
	std::vector<std::vector<Edge>> add;
	int64_t A, B;
	
	int distance;
	std::vector<int> query; // some common query vector

	/*
	int curSize;
	int subsize(int node, int par){
		int result=1;
		for(auto [child,_]: add[node]) if(child!=par) result+=subsize(child, node);
		return result;
	}
	int throwCentroid(int node, int par){
		int result=1, maxChild=0;
		for(auto [child,_]: add[node]) if(child!=par){
			auto const childSize=throwCentroid(child, node);
			maxChild=std::max(maxChild, childSize);
			result+=childSize;
		}
		if(std::max(maxChild, curSize-result)*2<=curSize) throw node;
		return result;
	}
	int centroid(int node){
		curSize=subsize(node, -1);
		try{
			throwCentroid(node, -1);
		}catch(int centroid){return centroid;}
		assert(false); __builtin_unreachable();
	}


	void work(int node){
		if(add[node].size()==1 and add[add[node][0]].size()==1){
			answer(node, add[node][0]);
			return;
		}

		node=centroid(node);
		std::vector<std::pair<int, Edge>> branches(add[node].size());
		std::transform(begin(add[node]), end(add[node]), branches.begin(),[&](auto edge){
			return std::pair(subsize(edge.node, node), edge);
		});
		std::sort(begin(branches), end(branches),[&](auto first, auto sec){return first.first<sec.first;});

		int split=0;
		{ // find a balanced split
			int left=0, right=curSize;
			while(split<(int)branches.size()){
				if(std::abs((left+branches[split].first)-(right-branches[split].first))<std::abs(left-right)){
					left+=branches[split].first;
					right-=branches[split].first;
					++split;
				}
			}
		}

		auto const toll=[&]{
			query.assign(add.size()-1, 0);
			for(int i=0; i<split; ++i){
				query[branches[i].second.index]=1;
				fillQuery(branches[i].second.node, node);
			}
			return ask(std::move(query);
		}();
		assert(A*distance<=toll); assert(toll<=B*distance);
		if(A*distance==toll){
		}else if(B*distance==toll){
		}else{
		}
	}
	*/

	void fillQuery(int node, int par){
		// fill all in subtree of node, not fill node..par
		for(auto [child, edgeIndex]: add[node]) if(child!=par){
			assert(query[edgeIndex]==0);
			query[edgeIndex]=1;
			fillQuery(child, node);
		}
	}

	std::vector<Edge> layer; // some nodes on the same layer, edgeIndex is the index of edge to parent
	void makeList(int node, int parent, int distance){
		for(auto [child, index]: add[node]) if(child!=parent){
			if(distance==1)
				layer.push_back({child, index});
			else
				makeList(child, node, distance-1);
		}
	}

	int solve1(int node, int parent, int distanceNode){
		assert(distanceNode>=0);
		if(distanceNode==0) return node;

		layer.clear();
		makeList(node, parent, distanceNode);
		int left=0;
		{
			int right=(int)layer.size();
			while(right-left>1){
				auto const mid=(left+right)>>1;
				query.assign(add.size()-1, 0);
				std::for_each(layer.begin()+left, layer.begin()+mid, [&](auto it){
					query[it.index]=1;
				});
				if(ask(std::move(query))>A*distance) right=mid; // [left..mid] contains the target
				else left=mid;
			}
		}
		return layer[left].node;
	}

	//std::pair<int, int> solve(){
	void solve(){
		assert(A<B);
		distance=int(ask(std::vector<int>(add.size()-1, 0))/A);
		//work(0);

		int left=0;
		{
			int right=(int)add.size()-1;
			while(right-left>1){
				auto const mid=(left+right)>>1;
				query.assign(add.size()-1, 0);
				std::fill(query.begin()+left, query.begin()+mid, 1);
				if(ask(std::move(query))>A*distance) right=mid;
				else left=mid;
			}
		}

		// now left is an edge on the S..T path
		int node, other;
		for(node=0;; ++node){
			for(auto [other_, edgeIndex]: add[node]) if(edgeIndex==left) {
				other=other_;
				goto break_outer;
			}
		}
break_outer:

		query.assign(add.size()-1, 0);
		fillQuery(node, other);
		auto const toll1=ask(std::move(query));
		auto const delta=toll1-A*distance;
		assert(delta%(B-A)==0);
		auto const distanceNode=int(delta/(B-A));

		auto const s=solve1(node, other, distanceNode);
		auto const t=solve1(other, node, distance-distanceNode-1);
		answer(s, t);
		// does "unspecified order" include "in parallel"?...
	}
};

void find_pair(int numNode, std::vector<int> U, std::vector<int> V, int A, int B) {
	int const numEdge = (int)U.size();
	if(numEdge!=numNode-1) return;

	Solve solve{{}, A, B};
	solve.add.resize(numNode);
	for(int index=0; index<numEdge; ++index){
		solve.add[U[index]].push_back({V[index], index});
		solve.add[V[index]].push_back({U[index], index});
	}

	/*
	auto const [s, t]=solve.solve();
  	answer(s, t);
	*/
	solve.solve();
}

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