제출 #440292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440292		rainboy	통행료 (IOI18_highway)	C++11	100 / 100	359 ms	9884 KiB

highway

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

using namespace std;

typedef vector<int> vi;

const int N = 90000, M = 130000;

int ii[M], jj[M];
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 hh[2][N - 1], mm[2];

void bfs(int n, int h) {
	static int cc[N], dd[N], qu[N];
	int i, head, cnt;

	for (i = 0; i < n; i++)
		dd[i] = n;
	head = cnt = 0;
	cc[ii[h]] = 0, dd[ii[h]] = 0, qu[head + cnt++] = ii[h];
	cc[jj[h]] = 1, dd[jj[h]] = 0, qu[head + cnt++] = jj[h];
	while (cnt) {
		int c, d, o;

		i = qu[cnt--, head++], c = cc[i], d = dd[i] + 1;
		for (o = eo[i]; o--; ) {
			int h = eh[i][o], j = i ^ ii[h] ^ jj[h];

			if (dd[j] > d) {
				ii[h] = i, jj[h] = j, hh[c][mm[c]++] = h;
				cc[j] = c, dd[j] = d, qu[head + cnt++] = j;
			}
		}
	}
}

void find_pair(int n, vi ii_, vi jj_, int a, int b) {
	int m = ii_.size(), h, h_, h1, i, j, c, lower, upper;
	vi ww(m, 0);
	long long d;

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

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'void append(int, int)':
highway.cpp:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  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: 18 / 18
• Subtask 6: 31 / 31