Submission #297730

#	Time	Username	Problem	Language	Result	Execution time	Memory
297730		eohomegrownapps	통행료 (IOI18_highway)	C++14	46 / 100	277 ms	15712 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;
vector<bool> visited;
vector<bool> visitededge;

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

int findedgeind(int numedges, int initial){
	int l = 0, r = numedges-1;
	vector<int> ans;
	while (l<=r){
		int mid = (l+r)/2;
		ans.assign(numedges,0);
		for (int i = 0; i<=mid; i++){
			ans[i]=1;
		}
		if (ask(ans)==initial){
			l=mid+1;
		} else {
			r=mid-1;
		}
	}
	return l;
}

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.assign(n,vector<pair<int,int>>());
	parentnode.resize(n,-1);
	parentedge.resize(m,-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});
		//cout<<U[i]<<' '<<V[i]<<endl;
	}
	
	vector<int> query(m);
	ll len = ask(query)/a;

	int edgeind = findedgeind(m,len*a);
	int root = U[edgeind];

	visited.assign(n,false);
	visitededge.assign(m,false);

	query.assign(m,1);

	parentnode[root]=-1;
	parentedge[root]=-1;

	dfs(root,-1);

	// binary search until path is len*b
	int l = 0, r = n-1;
	query.assign(m,1);
	while (l<=r){
		int mid = (l+r)/2;
		for (int i = 1; i<=mid; i++){
			query[parentedge[preorder[i]]]=1;
		}
		for (int i = mid+1; i<n; i++){
			query[parentedge[preorder[i]]]=0;
		}
		ll ans = ask(query);
		if (ans<len*b){
			l=mid+1;
		} else {
			r=mid-1;
		}
	}
	root = preorder[l];
	//cout<<root<<endl;
	// root at l, then search again
	preorder.clear();
	parentnode[root]=-1;
	parentedge[root]=-1;
	visited.assign(n,false);
	visitededge.assign(m,false);
	dfs(root,-1);
	l = 0, r = n-1;
	while (l<=r){
		int mid = (l+r)/2;
		for (int i = 1; i<=mid; i++){
			query[parentedge[preorder[i]]]=1;
		}
		for (int i = mid+1; i<n; i++){
			query[parentedge[preorder[i]]]=0;
		}
		ll ans = ask(query);
		if (ans<len*b){
			l=mid+1;
		} else {
			r=mid-1;
		}
	}
	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:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i<U.size(); i++){
      |                  ~^~~~~~~~~

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