Submission #253709

#	Time	Username	Problem	Language	Result	Execution time	Memory
253709		Lawliet	Highway Tolls (IOI18_highway)	C++17	51 / 100	237 ms	29688 KiB

highway

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

using namespace std;
typedef long long int lli;

const int MAXN = 90010;

int n, m;
int A, B;

int depth[MAXN];
int ancEdge[MAXN];

lli dist;

vector<int> adj[MAXN];
vector<int> level[MAXN];
vector<int> indEdge[MAXN];

void DFSInit(int cur, int p, int d)
{
	depth[cur] = d;
	level[d].push_back( cur );

	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];
		int ind = indEdge[cur][i];

		if( viz == p ) continue;

		ancEdge[viz] = ind;
		DFSInit( viz , cur , d + 1 );
	}
}

vector<int> activeNodes(int L, int R)
{
	vector<int> c( m , 0 );

	for(int p = L ; p <= R ; p++)
	{
		for(int i = 0 ; i < (int)level[p].size() ; i++)
		{
			int cur = level[p][i];
			c[ ancEdge[cur] ] = 1;
		}
	}

	return c;
}

vector<int> activeNodes(int L, int R, int d)
{
	vector<int> c( m , 0 );

	for(int i = L ; i <= R ; i++)
	{
		int cur = level[d][i];
		c[ ancEdge[cur] ] = 1;
	}

	return c;
}

int findMaxDepth()
{
	int l = 0;
  	int r = n - 1;

  	while( l < r )
  	{
  		int m = ( l + r )/2;

  		if( ask( activeNodes( 1 , m ) ) == dist*B ) r = m;
  		else l = m + 1;
  	}

  	return r;
}

int findNode(int depth)
{
	int l = 0;
	int r = (int)level[depth].size() - 1;

	while( l < r )
	{
		int m = ( l + r )/2;

		if( ask( activeNodes( 0 , m , depth ) ) != dist*A ) r = m;
		else l = m + 1;
	}

	return level[depth][r];
}

void find_pair(int N, vector<int> U, vector<int> V, int a, int b) 
{
	A = a; B = b;
	n = N; m = (int)U.size();

	dist = ask( vector<int>( m , 0 ) )/A;

	for(int i = 0 ; i < m ; i++)
	{
		adj[ U[i] ].push_back( V[i] );
		adj[ V[i] ].push_back( U[i] );

		indEdge[ U[i] ].push_back( i );
		indEdge[ V[i] ].push_back( i );
	}

  	DFSInit( 0 , 0 , 0 );

  	int maxDepth = findMaxDepth();
  	int S = findNode( maxDepth );

  	for(int i = 0 ; i < n ; i++)
  		level[i].clear();

  	DFSInit( S , S , 0 );
  	int T = findNode( dist );

  	answer( S , T );
}

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