Submission #544750

#	Time	Username	Problem	Language	Result	Execution time	Memory
544750		rainboy	Valley (BOI19_valley)	C11	100 / 100	228 ms	37452 KiB

valley

#include <stdio.h>
#include <stdlib.h>

#define N	100000
#define L	16	/* L = floor(log2(N)) */
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }

int ii[N - 1], jj[N - 1], ww[N - 1];
int *oh[N], oo[N];

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

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

char shop[N]; int dd[N], pp[N][L + 1]; long long xx[N], xx_[N], yy[N][L + 1];

void dfs1(int p, int i, int d, long long x) {
	int o, l;

	dd[i] = d, xx[i] = x, xx_[i] = shop[i] ? x : INF;
	pp[i][0] = p;
	for (l = 1; 1 << l <= d; l++)
		pp[i][l] = pp[pp[i][l - 1]][l - 1];
	for (o = oo[i]; o--; ) {
		int h = oh[i][o], j = i ^ ii[h] ^ jj[h];

		if (j != p) {
			ii[h] = i, jj[h] = j, dfs1(i, j, d + 1, x + ww[h]);
			xx_[i] = min(xx_[i], xx_[j]);
		}
	}
}

void dfs2(int p, int i) {
	int o, l;

	yy[i][0] = xx_[i] == INF ? INF : xx_[i] - xx[i] * 2;
	for (l = 1; 1 << l <= dd[i]; l++)
		yy[i][l] = min(yy[i][l - 1], yy[pp[i][l - 1]][l - 1]);
	for (o = oo[i]; o--; ) {
		int h = oh[i][o], j = i ^ ii[h] ^ jj[h];

		if (j != p)
			dfs2(i, j);
	}
}

long long query(int i, int j) {
	int i_, l;
	long long y;

	if (dd[i] < dd[j])
		return -1;
	y = INF;
	for (i_ = i, l = L; l >= 0; l--)
		if (1 << l <= dd[i_] - dd[j])
			y = min(y, yy[i_][l]), i_ = pp[i_][l];
	if (i_ != j)
		return -1;
	y = min(y, yy[i_][0]);
	return y == INF ? INF : y + xx[i];
}

int main() {
	int n, k, q, r, h, i, j;

	scanf("%d%d%d%d", &n, &k, &q, &r), r--;
	for (i = 0; i < n; i++)
		oh[i] = (int *) malloc(2 * sizeof *oh[i]);
	for (h = 0; h < n - 1; h++) {
		int w;

		scanf("%d%d%d", &i, &j, &w), i--, j--;
		ii[h] = i, jj[h] = j, ww[h] = w;
		append(i, h), append(j, h);
	}
	while (k--) {
		scanf("%d", &i), i--;
		shop[i] = 1;
	}
	dfs1(-1, r, 0, 0);
	dfs2(-1, r);
	while (q--) {
		long long ans;

		scanf("%d%d", &h, &i), h--, i--;
		ans = query(i, jj[h]);
		if (ans == -1)
			printf("escaped\n");
		else if (ans == INF)
			printf("oo\n");
		else
			printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

valley.c: In function 'append':
valley.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
valley.c: In function 'main':
valley.c:73:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d%d%d%d", &n, &k, &q, &r), r--;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.c:79:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%d%d%d", &i, &j, &w), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.c:84:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d", &i), i--;
      |   ^~~~~~~~~~~~~~~
valley.c:92:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%d%d", &h, &i), h--, i--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41