Submission #141544

#	Time	Username	Problem	Language	Result	Execution time	Memory
141544		Lawliet	Highway Tolls (IOI18_highway)	C++14	51 / 100	338 ms	22248 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
 
#define MAX 90010
 
using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;
 
int N, A, B;
 
int prof[MAX];
int paiEdge[MAX];

lli distA;
lli distB;
 
vector<int> grafo[MAX];
vector<int> indEdge[MAX];
vector<int> distNode[MAX];

vector<pii> searchSpace;

void DFS(int i, int p)
{
	distNode[ prof[i] ].push_back( i );

	//printf("i = %d    %d\n",i,prof[i]);

	for(int g = 0 ; g < grafo[i].size() ; g++)
	{
		int prox = grafo[i][g];
		int ind = indEdge[i][g];

		if(prox == p) continue;

		paiEdge[ prox ] = ind;
		prof[ prox ] = prof[ i ] + 1;

		DFS(prox , i);
	}
}

void initDFS()
{
	for(int g = 0 ; g <= N ; g++)
		distNode[ g ].clear();
}

bool test(int l, int r)
{
	vector<int> query(N - 1 , 0);

	for(int g = l ; g <= r ; g++)
	{
		int cur = searchSpace[ g ].second;

		query[ cur ] = 1;
	}

	lli aux = ask( query );

	return aux != distA;
}

bool test(int k)
{
	vector<int> query(N - 1 , 0);

	for(int g = 1 ; g < N ; g++)
		if(prof[g] <= k) query[ paiEdge[g] ] = 1;
	//printf("oi\n");
	lli aux = ask( query );

	return aux == distB;
}

int find(int root, int d)
{
	initDFS(); prof[ root ] = 0;
	DFS(root , root);

	searchSpace.clear();

	for(int g = 0 ; g < distNode[ d ].size() ; g++)
	{
		int prox = distNode[d][g];
		searchSpace.push_back({ prox , paiEdge[ prox ] });
	}

	int l = 0, r = searchSpace.size() - 1;

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

		if(test(l , m)) r = m;
		else l = m + 1;
	}

	return searchSpace[ l ].first;
}
 
void find_pair(int n, vector<int> U, vector<int> V, int a, int b)
{
	N = n; A = a; B = b;
 
	for(int g = 0 ; g < N - 1 ; g++)
	{
		int i = U[g];
		int j = V[g];

		grafo[ i ].push_back( j );
		grafo[ j ].push_back( i );

		indEdge[ i ].push_back( g );
		indEdge[ j ].push_back( g );
	}

	vector<int> nullVector(N - 1 , 0);

	distA = ask( nullVector );
	distB = distA/A; distB *= B;

	DFS(0 , 0);

	int l = 0, r = n - 1;

	//printf("---- %lld %lld\n",distA,distB);

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

		//printf("L = %d  R = %d\n",l,r);

		if(test(m)) r = m;
		else l = m + 1;
	}

	//printf("PROF = %d\n",r);

	int S = find(0 , r);
	int T = find(S , distA/A);

	answer(S , T);
}

Compilation message (stderr)

highway.cpp: In function 'void DFS(int, int)':
highway.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < grafo[i].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'int find(int, int)':
highway.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < distNode[ d ].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~

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