Submission #297388

#	Time	Username	Problem	Language	Result	Execution time	Memory
297388		eohomegrownapps	Highway Tolls (IOI18_highway)	C++14	51 / 100	316 ms	262148 KiB

highway

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

typedef long long ll;

// ll ask(vector<int> w)
// void answer(int a, int b)

vector<vector<pair<int,int>>> adjlist; // node, ind

int n,a,b,m;

vector<int> parentedge;
vector<int> parentnode;

vector<int> preorder;

void dfs(int node, int par){
	preorder.push_back(node);
	for (auto p : adjlist[node]){
		int i = p.first;
		int ni = p.second;
		if (i==par){continue;}
		parentnode[i]=node;
		parentedge[i]=ni;
		dfs(i,node);
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n=N;a=A;b=B;m=U.size();
	adjlist.resize(n);
	parentnode.resize(n,-1);
	parentedge.resize(n,-1);
	for (int i = 0; i<U.size(); i++){
		adjlist[U[i]].push_back({V[i],i});
		adjlist[V[i]].push_back({U[i],i});
	}
	dfs(0,-1);

	// what's the total length of the path?
	vector<int> query(m);
	ll len = ask(query)/a;

	// binary search until path is len*b
	int l = 0, r = n-1;
	while (l<=r){
		int mid = (l+r)/2;
		query.assign(m,0);
		for (int i = 1; i<=mid; i++){
			query[parentedge[preorder[i]]]=1;
		}
		ll ans = ask(query);
		if (ans<len*b){
			l=mid+1;
		} else {
			r=mid-1;
		}
	}
	int root = preorder[l];
	// root at l, then search again
	preorder.clear();
	parentnode[root]=-1;
	parentedge[root]=-1;
	dfs(root,-1);
	l = 0, r = n-1;
	while (l<=r){
		int mid = (l+r)/2;
		query.assign(m,0);
		for (int i = 1; i<=mid; i++){
			query[parentedge[preorder[i]]]=1;
		}
		ll ans = ask(query);
		if (ans<len*b){
			l=mid+1;
		} else {
			r=mid-1;
		}
	}
	//cout<<root<<' '<<preorder[l]<<'\n';
	answer(root,preorder[l]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i = 0; i<U.size(); i++){
      |                  ~^~~~~~~~~

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