제출 #440246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440246		rainboy	Highway Tolls (IOI18_highway)	C++11	69 / 100	317 ms	9652 KiB

highway

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

using namespace std;

typedef vector<int> vi;

const int N = 90000, M = 130000;

int ii[M], jj[M];
int *eh[N], eo[N], 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[N - 1];

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

	for (i = 0; i < n; i++)
		dd[i] = n;
	head = cnt = 0, m_ = 0;
	dd[s] = 0, qu[head + cnt++] = s;
	while (cnt) {
		int d, o;

		i = qu[cnt--, head++], 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[m_++] = h, dd[j] = d, qu[head + cnt++] = j;
		}
	}
}

vi ww; int a, b; long long d;

int ask_(int k) {
	static char marked[N];
	int h, i;

	memset(marked, 0, n * sizeof *marked);
	for (h = k - 1; h < n - 1; h++)
		marked[jj[hh[h]]] = 1;
	for (h = 0; h < n - 1; h++)
		ww[hh[h]] = !marked[ii[hh[h]]] && marked[jj[hh[h]]];
	return (ask(ww) - d) / (b - a);
}

int i, j;

void solve(int l, int r, int mask) {
	int m = (l + r + 1) / 2, x;

	if (mask == 0)
		return;
	if (l == r) {
		if (mask == 1)
			i = l == 0 ? ii[hh[0]] : jj[hh[l - 1]];
		else
			j = l == 0 ? ii[hh[0]] : jj[hh[l - 1]];
		return;
	}
	x = ask_(m);
	solve(l, m - 1, mask & ((x != 2) | (x == 0) << 1)), solve(m, r, mask & ((x == 2) | (x != 0) << 1));
}

void find_pair(int n_, vi ii_, vi jj_, int a_, int b_) {
	int m = ii_.size(), h, lower, upper;

	ww.resize(m);
	n = n_, a = a_, b = b_;
	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 = n;
	while (upper - lower > 1) {
		i = (lower + upper) / 2;
		for (h = 0; h < m; h++)
			ww[h] = ii[h] <= i || jj[h] <= i;
		if (ask(ww) > d)
			upper = i;
		else
			lower = i;
	}
	bfs(n, upper);
	for (h = 0; h < m; h++)
		ww[h] = 1;
	solve(0, n - 1, 3);
	answer(i, j);
}

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

highway.cpp: In function 'void append(int, int)':
highway.cpp:17:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   17 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
highway.cpp: In function 'int ask_(int)':
highway.cpp:49:9: warning: unused variable 'i' [-Wunused-variable]
   49 |  int h, i;
      |         ^

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