Submission #117002

#	Time	Username	Problem	Language	Result	Execution time	Memory
117002		dsjong	Highway Tolls (IOI18_highway)	C++14	12 / 100	423 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
int NN;
long long AA,BB,CNT;
vector<int>adj[100005];
int dep[100005],par[100005];
int mp[100005];
vector<int>leaves;
void dfs(int i,int p){
	par[i]=p;
	for(int j:adj[i]){
		if(j==p) continue;
		dep[j]=dep[i]+1;
		dfs(j,i);
	}
}
bool pick[100005];
bool vis[100005];
vector<int>query;
bool check(int L,int R){
	query.clear();
	memset(pick,0,sizeof pick);
	memset(vis,0,sizeof vis);
	for(int i=L;i<=R;i++){
		int cur=leaves[i];
		while(!vis[cur]&&cur!=0){
			pick[mp[cur]]=true;
			vis[cur]=true;
			cur=par[cur];
		}
	}
	int cnt=0;
	for(int i=0;i<NN-1;i++){
		if(pick[i]){
			query.push_back(1);
			cnt++;
		}
		else query.push_back(0);
	}
	long long x=ask(query);
	if(x/BB>=CNT) return true;
	return false;
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int a, int b) {
	NN=n,AA=a,BB=b;
	for(int i=0;i<U.size();i++){
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	dep[0]=0;
	dfs(0,-1);
	for(int i=0;i<U.size();i++){
		if(par[U[i]]==V[i]) mp[U[i]]=i;
		else mp[V[i]]=i;
	}
	query.clear();
	for(int i=0;i<NN-1;i++){
		query.push_back(0);
	}
	CNT=ask(query)/AA;
	//cout<<CNT<<endl;
	for(int i=1;i<NN;i++){
		if(adj[i].size()==1) leaves.push_back(i);
	}
	
	/*for(int i:leaves) cout<<i<<" ";
	cout<<endl;*/
	int L=0,R=leaves.size()-1;
	while(L<R){
		//cout<<L<<" "<<R<<" ";
		if(R==L+1){
			if(check(L,L)) R=L;
			else L=R;
			break;
		}
		int M=(L+R)/2;
		if(check(L,M)) R=M;
		else L=M+1;
	}
	int ans=leaves[L];
	for(int i=0;i<dep[leaves[L]]-CNT;i++){
		ans=par[ans];
		//cout<<ans<<endl;
	}
	answer(ans,0);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<U.size();i++){
              ~^~~~~~~~~
highway.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<U.size();i++){
              ~^~~~~~~~~

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