Submission #119284

#	Time	Username	Problem	Language	Result	Execution time	Memory
119284		joseacaz	Highway Tolls (IOI18_highway)	C++17	51 / 100	232 ms	18048 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define MAXN 90005
#define MAXM 130005

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N, M, pathLength, S, T;
ll A, B;
vector < int > U, V, Q;
vector < pii > Graph[MAXN];
vector < pair < int, pii > > nodes;

bool bin ( int x )
{
	fill ( Q.begin(), Q.begin() + x + 1, 1 );
	fill ( Q.begin() + x + 1, Q.end(), 0 );

	ll tmp = ask ( Q );
	if ( tmp != A * pathLength )
		return true;
	return false;
}

bool bin2 ( int x )
{
	fill ( Q.begin(), Q.end(), 1 );
	for ( int i = x; i < nodes.size(); i++ )
		Q[nodes[i].second.first] = 0;

	ll tmp = ask ( Q );
	return (tmp == B * pathLength);
}

void dfs ( int node, int parent = -1, int depth = 0 )
{
	for ( auto i : Graph[node] )
		if ( i.first != parent )
			dfs ( i.first, node, depth + 1 ), nodes.push_back ( {depth, {i.second, i.first}} );
}

int solve ( int node )
{
	sort ( nodes.begin(), nodes.end() );

	int s = 0, e = nodes.size(), mid, val, ans;
	while ( s <= e )
	{
		mid = (s + e) / 2;
		val = bin2 ( mid );

		if ( val )
			ans = mid, e = mid - 1;
		else
			s = mid + 1;
	}

	if ( ans == 0 )
		return node;
	return nodes[ans - 1].second.second;
}

void find_pair ( int _N, vector<int> _U, vector<int> _V, int _A, int _B )
{
	N = _N;
	M = _U.size();
	A = _A;
	B = _B;
	swap ( U, _U );
	swap ( V, _V );
	for ( int i = 0; i < M; i++ )
	{
		Graph[U[i]].push_back ( {V[i], i} );
		Graph[V[i]].push_back ( {U[i], i} );
	}
	Q.resize ( M );

	if ( M == N - 1 )
	{
		//Graph is a tree, 51 points
		for ( auto &i : Q )
			i = 0;
		pathLength = ask ( Q ) / A;

		int s = 0, e = M - 1, mid, val, edge;
		while ( s <= e )
		{
			mid = (s + e) / 2;
			val = bin ( mid );

			if ( val )
				edge = mid, e = mid - 1;
			else
				s = mid + 1;
		}

		nodes.clear();
		dfs ( U[edge], V[edge] );
		S = solve ( U[edge] );

		nodes.clear();
		dfs ( V[edge], U[edge] );
		T = solve ( V[edge] );

		answer ( S, T );
	}
}

Compilation message (stderr)

highway.cpp: In function 'bool bin2(int)':
highway.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for ( int i = x; i < nodes.size(); i++ )
                   ~~^~~~~~~~~~~~~~
highway.cpp: In function 'int solve(int)':
highway.cpp:62:19: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return nodes[ans - 1].second.second;
               ~~~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:100:24: warning: 'edge' may be used uninitialized in this function [-Wmaybe-uninitialized]
   dfs ( U[edge], V[edge] );
                        ^

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