Submission #556048

#	Time	Username	Problem	Language	Result	Execution time	Memory
556048		jamezzz	Highway Tolls (IOI18_highway)	C++17	12 / 100	239 ms	262144 KiB

highway

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
#define pf printf
#define pb push_back

#define maxn 900005

int par[maxn],pedge[maxn],dep[maxn];
vector<ii> AL[maxn];
vector<int> pos;
int n,m,a,b;
ll d;

void dfs(int u){
	for(auto[v,i]:AL[u]){
		if(v==par[u])continue;
		par[v]=u;
		pedge[v]=i;
		dep[v]=dep[u]+1;
		dfs(v);
	}
}

inline void proc(){
	while(pos.size()!=1){
		int x=pos.size()/2;
		vi w(m);
		for(int i=0;i<x;++i)w[pedge[pos[i]]]=1;
		vi tmp;
		if(ask(w)>d*a){
			for(int i=0;i<x;++i)tmp.pb(pos[i]);
		}
		else{
			for(int i=x;i<pos.size();++i)tmp.pb(pos[i]);
		}
		swap(tmp,pos);
		w.clear();
		tmp.clear();
	}
}

void find_pair(int _n,vi u,vi v,int _a,int _b){
	n=_n;a=_a;b=_b;
	m=u.size();
	for(int i=0;i<m;++i){
		AL[u[i]].pb({v[i],i});
		AL[v[i]].pb({u[i],i});
	}
	
	memset(par,-1,sizeof par);
	vi w(m);
	d=ask(w)/a;
	dfs(0);
	
	int lo=1,hi=0,mid,res;
	for(int i=0;i<n;++i)hi=max(hi,dep[i]);
	while(lo<=hi){
		mid=(lo+hi)/2;
		vi w(m);
		for(int i=0;i<n;++i){
			if(dep[i]==mid)w[pedge[i]]=1;
		}
		if(ask(w)>d*a)res=mid,lo=mid+1;
		else hi=mid-1;
		w.clear();
	}
	
	for(int i=0;i<n;++i){
		if(dep[i]==res)pos.pb(i);
	}
	proc();
	int s=pos[0];
	
	memset(par,-1,sizeof par);
	dep[s]=0;
	dfs(s);
	
	pos.clear();
	for(int i=0;i<n;++i){
		if(dep[i]==d)pos.pb(i);
	}
	proc();
	int t=pos[0];
	
	answer(s,t);
}

Compilation message (stderr)

highway.cpp: In function 'void proc()':
highway.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for(int i=x;i<pos.size();++i)tmp.pb(pos[i]);
      |                ~^~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:74:3: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |   if(dep[i]==res)pos.pb(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