Submission #435630

#	Time	Username	Problem	Language	Result	Execution time	Memory
435630		CaroLinda	Highway Tolls (IOI18_highway)	C++14	51 / 100	279 ms	10236 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

#define sz(x) (int)(x.size())
#define ll long long
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pii pair<int,int>
#define mk make_pair
#define all(x) x.begin(),x.end()
#define pb push_back

const int MAX = 90010 ;

using namespace std ;

int N , A , B , M ;
int group[MAX] ;
vector<int> toAsk ;
vector<pii> adj[MAX] ;
int dist[2][MAX] ;
long long C ;
vector<int> ans ;

void bfsDist(int S, int idx )
{
	for(int i = 0  ; i < N ; i++ ) dist[idx][i] = M+10 ;
	dist[idx][S] = 0 ;

	vector<int> fila = {S} ;
	int ini = 0 ;

	while(ini < sz(fila))
	{
		int x = fila[ini++] ;

		for(auto e : adj[x])
		{
			if(dist[idx][e.ff] <= dist[idx][x]+1 ) continue ;
			dist[idx][e.ff] = dist[idx][x]+1 ;
			fila.pb(e.ff) ;			
		}

	}

}

void bfs(int S, int idx )
{
	vector<int> fila = {S} , edge ;
	int ini = 0 ;

	group[S] = -1 ;

	while(ini < sz(fila))
	{
		int x = fila[ini++] ;

		for(auto e : adj[x] ) 
		{
			if(group[e.ff] != idx ) continue ;
			
			group[e.ff] = -1 ;
			fila.pb(e.ff) ;
			edge.pb(e.ss) ;
		}

	}

	/*cout << S <<": " ;
	for(auto e : edge )cout << e <<" " ;
	cout << endl ; */

	int l = 0 , r = sz(edge)-1 , mid , best = -1; 
	while(l <= r )
	{
		mid = (l+r)>>1 ;

		lp(i,0,M) toAsk[i] = 1 ;
		for(int i = mid+1 ; i < sz(edge) ; i++ ) toAsk[ edge[i] ] = 0 ;

		ll c = ask(toAsk) ;

		if( c == (C/A)*(ll)B ) 
		{
			r = mid-1 ;
			best = mid ;
		}
		else l = mid+1 ;
	} 
	if(best == 0)
	{
		lp(i,0,M) toAsk[i] = 1 ;
		for(auto e : edge ) toAsk[e] = 0 ;
		if(ask(toAsk) == (C/A)*(ll)B ) best = -1 ;
	}

	ans.pb(fila[best+1]) ;
}

void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B) 
{
	N = _N ;
	A = _A ;
	B = _B ;
	M = sz(U) ;

	for(int i = 0 ; i < M ; i++ )
		for(int j = 0 ; j < 2 ; j++ , swap(U[i] , V[i]))
			adj[U[i]].pb( mk(V[i],i) ) ;

	lp(i,0,M) toAsk.pb(0) ;

	C = ask(toAsk);

	int l = 0 , r = sz(U)-1 , mid , best = 0 ;
	while(l <= r )
	{
		mid = (l+r)>>1 ;
		
		for(int i = 0 ; i <= mid ; i++ ) toAsk[i] = 1 ;
		for(int i = mid+1 ; i < M ; i++ ) toAsk[i] = 0 ;

		if(ask(toAsk) != C ) 
		{
			best = mid ;
			r = mid-1 ;
		}
		else l = mid+1 ;
	}

	bfsDist( U[best] , 0 ) ;
	bfsDist( V[best] , 1 ) ;

	for(int i = 0 ; i < N ; i++ )
	{
		if( dist[0][i] == dist[1][i] ) group[i] = -1 ;
		else if( dist[0][i] > dist[1][i] ) group[i] = 1 ;
	}

	bfs(U[best] , 0 ) ;
	bfs(V[best] , 1 ) ;

	answer(ans[0] , ans[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