Submission #556123

#	Time	Username	Problem	Language	Result	Execution time	Memory
556123		jamezzz	Highway Tolls (IOI18_highway)	C++17	51 / 100	186 ms	10736 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 all(x) x.begin(),x.end()

#define maxn 90005

int n,m,a,b,dist[maxn][2],pedge[maxn][2],s[maxn];
ll d;
vector<ii> AL[maxn];

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});
	}
	
	vi w(m);
	d=ask(w)/a;
	
	vi pos;
	for(int i=0;i<m;++i)pos.pb(i);
	while(pos.size()!=1){
		int x=pos.size();
		vi w(m);
		for(int i=0;i<x/2;++i)w[pos[i]]=1;
		vi tmp;
		if(ask(w)>d*a){
			for(int i=0;i<x/2;++i)tmp.pb(pos[i]);
		}
		else{
			for(int i=x/2;i<x;++i)tmp.pb(pos[i]);
		}
		swap(tmp,pos);
		tmp.clear();
	}
	int f=pos[0];
	vi r={u[f],v[f]};
	
	//pf("rts: %d %d\n",r[0],r[1]);
	
	memset(dist,-1,sizeof dist);
	for(int i=0;i<2;++i){
		queue<int> q;
		dist[r[i]][i]=0;
		q.push(r[i]);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(auto[v,x]:AL[u]){
				if(dist[v][i]!=-1)continue;
				dist[v][i]=dist[u][i]+1;
				pedge[v][i]=x;
				q.push(v);
			}
		}
	}
	/*
	pf("d[0]: ");
	for(int i=0;i<n;++i)pf("%d ",dist[i][0]);
	pf("\n");
	pf("d[1]: ");
	for(int i=0;i<n;++i)pf("%d ",dist[i][1]);
	pf("\n");
	*/
	//pf("s: ");
	for(int i=0;i<n;++i){
		if(dist[i][1]<dist[i][0])s[i]=1;
		//pf("%d ",s[i]);
	}
	//pf("\n");
	vi ans={0,0};
	for(int x=0;x<2;++x){
		vi pos;
		for(int i=0;i<n;++i){
			if(s[i]==x&&i!=r[x])pos.pb(pedge[i][x]);
		}
		//pf("pos %d: ",x);
		//for(int i:pos)pf("%d ",i);
		//pf("\n");
		vi w(m,1);
		for(int i:pos)w[i]=0;
		//pf("w %d: ",x);
		//for(int i=0;i<m;++i)pf("%d ",w[i]);
		//pf("\n");
		sort(all(pos),[&](int a,int b){return max(dist[u[a]][x],dist[v[a]][x])<max(dist[u[b]][x],dist[v[b]][x]);});
		int lo=0,hi=pos.size()-1,mid,res=-1;
		while(lo<=hi){
			int mid=(lo+hi)>>1;
			for(int i=0;i<=mid;++i)w[pos[i]]=1;
			//pf("mid %d: %d\n",mid,ask(w));
			if(ask(w)==d*b)res=mid,hi=mid-1;
			else lo=mid+1;
			for(int i=0;i<=mid;++i)w[pos[i]]=0;
		}
		if(res==0&&ask(w)==d*b)res=-1;
		//pf("res %d: %d\n",x,res);
		if(res==-1)ans[x]=r[x];
		else{
			int e=pos[res];
			ans[x]=(dist[u[e]][x]>dist[v[e]][x])?u[e]:v[e];
		}
	}
	//pf("%d %d\n",ans[0],ans[1]);
	answer(ans[0],ans[1]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:95:28: warning: unused variable 'mid' [-Wunused-variable]
   95 |   int lo=0,hi=pos.size()-1,mid,res=-1;
      |                            ^~~

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