Submission #435762

#	Time	Username	Problem	Language	Result	Execution time	Memory
435762		CaroLinda	Highway Tolls (IOI18_highway)	C++14	100 / 100	432 ms	12124 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 , ans , toxic ;
vector<pii> adj[MAX] ;
int dist[2][MAX] ;
long long C ;

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, int X )
{
	vector<int> fila = {S} , edge , edge2 ;
	int ini = 0 ;

	group[S] = -1 ;

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

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

			group[e.ff] = -1 ;
			fila.pb(e.ff) ;
			edge.pb(e.ss) ;
		}

	}

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

		lp(i,0,M) toAsk[i] = 0 ;
		for(auto e : toxic ) toAsk[e] = 1 ;
		for(auto e : edge2 ) toAsk[e] = 1 ;
		for(int i = mid ; i < sz(edge) ; i++ ) toAsk[edge[i]] = 1 ;
		toAsk[X] = 0 ;

		if( ask(toAsk) == C )
		{
			best = mid-1 ;
			r = mid-1 ;
		}
		else l = mid+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 ;
	}

	for(int i = 0 ; i < M ; i++ )
	{
		if( group[U[i]] != -1 && group[U[i]] == group[V[i]] ) continue ;
		if(i == best) continue ;
		toxic.pb(i) ;	
	}

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

	answer(ans[0] , ans[1]) ;
}

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