Submission #440208

#	Time	Username	Problem	Language	Result	Execution time	Memory
440208		rainboy	Highway Tolls (IOI18_highway)	C++11	51 / 100	261 ms	15000 KiB

highway

#include "highway.h"
#include <stdlib.h>

using namespace std;

typedef vector<int> vi;

const int N = 90000;

int *eh[N], eo[N];

void append(int i, int h) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

int ii[N - 1], jj[N - 1], hh[N - 1], m;

void dfs(int p, int i) {
	int o;

	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ii[h] ^ jj[h];

		if (j != p) {
			ii[h] = i, jj[h] = j;
			dfs(i, j);
			hh[m++] = h;
		}
	}
}

void find_pair(int n, vi ii_, vi jj_, int a, int b) {
	vi ww(n - 1, 0);
	int h, i, j, lower, upper;
	long long d;

	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < n - 1; h++) {
		i = ii[h] = ii_[h], j = jj[h] = jj_[h];
		append(i, h), append(j, h);
	}
	d = ask(ww);
	lower = -1, upper = n;
	while (upper - lower > 1) {
		i = (lower + upper) / 2;
		for (h = 0; h < n - 1; h++)
			ww[h] = ii[h] <= i || jj[h] <= i;
		if (ask(ww) > d)
			upper = i;
		else
			lower = i;
	}
	i = upper;
	m = 0, dfs(-1, i);
	lower = -1, upper = n - 1;
	while (upper - lower > 1) {
		int h_ = (lower + upper) / 2;

		for (h = 0; h < n - 1; h++)
			ww[hh[h]] = h <= h_;
		if (ask(ww) > d)
			upper = h_;
		else
			lower = h_;
	}
	i = jj[hh[upper]];
	m = 0, dfs(-1, i);
	lower = -1, upper = n - 1;
	while (upper - lower > 1) {
		int h_ = (lower + upper) / 2;

		for (h = 0; h < n - 1; h++)
			ww[hh[h]] = h <= h_;
		if (ask(ww) > d)
			upper = h_;
		else
			lower = h_;
	}
	answer(i, jj[hh[upper]]);
}

Compilation message (stderr)

highway.cpp: In function 'void append(int, int)':
highway.cpp:15:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   15 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

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