oj.uz

답안 #545428

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545428 2022-04-04T13:46:28 Z rainboy 공장들 (JOI14_factories) C
100 / 100
 3957 ms 207604 KB 
#include "factories.h"
#include <stdlib.h>
#include <string.h>

#define N	500000
#define LN	18	/* LN = floor(log2(N)) */
#define INF	0x3f3f3f3f3f3f3f3fLL

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

int *ej[N], *ew[N], eo[N], n;

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

	if (o >= 2 && (o & o - 1) == 0) {
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
		ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
	}
	ej[i][o] = j, ew[i][o] = w;
}

int sz[N], c;

void dfs1(int p, int i, int n) {
	int o, centroid;

	sz[i] = 1, centroid = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			dfs1(i, j, n);
			sz[i] += sz[j];
			if (sz[j] * 2 > n)
				centroid = 0;
		}
	}
	if ((n - sz[i]) * 2 > n)
		centroid = 0;
	if (centroid)
		c = i;
}

void delete(int i, int j) {
	int o;

	for (o = eo[i]; o--; )
		if (ej[i][o] == j) {
			eo[i]--;
			while (o < eo[i])
				ej[i][o] = ej[i][o + 1], ew[i][o] = ew[i][o + 1], o++;
			return;
		}
}

int cc[N][LN + 1], kk[N]; long long dd[N][LN + 1];

void dfs2(int p, int i, long long d) {
	int o;

	cc[i][kk[i]] = c, dd[i][kk[i]] = d, kk[i]++;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o], w = ew[i][o];

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

void cd(int i, int n) {
	int o;

	dfs1(-1, i, n), i = c;
	dfs2(-1, i, 0);
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		delete(j, i);
		cd(j, sz[j] < sz[i] ? sz[j] : n - sz[i]);
	}
}

long long dd_[N];

void Init(int n_, int ii[], int jj[], int ww[]) {
	int h, i;

	n = n_;
	for (i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		ew[i] = (int *) malloc(2 * sizeof *ew[i]);
	}
	for (h = 0; h < n - 1; h++) {
		append(ii[h], jj[h], ww[h]), append(jj[h], ii[h], ww[h]);
	}
	cd(0, n);
	memset(dd_, 0x3f, n * sizeof *dd_);
}

long long Query(int n1, int ii1[], int n2, int ii2[]) {
	int g, h, i, c;
	long long ans;

	for (h = 0; h < n1; h++) {
		i = ii1[h];
		for (g = 0; g < kk[i]; g++) {
			c = cc[i][g];
			dd_[c] = min(dd_[c], dd[i][g]);
		}
	}
	ans = INF;
	for (h = 0; h < n2; h++) {
		i = ii2[h];
		for (g = 0; g < kk[i]; g++) {
			c = cc[i][g];
			ans = min(ans, dd_[c] + dd[i][g]);
		}
	}
	for (h = 0; h < n1; h++) {
		i = ii1[h];
		for (g = 0; g < kk[i]; g++) {
			c = cc[i][g];
			dd_[c] = INF;
		}
	}
  return ans;
}

Compilation message

factories.c: In function 'append':
factories.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 980 KB Output is correct
2 Correct 294 ms 10584 KB Output is correct
3 Correct 307 ms 10572 KB Output is correct
4 Correct 306 ms 10592 KB Output is correct
5 Correct 327 ms 11000 KB Output is correct
6 Correct 231 ms 10656 KB Output is correct
7 Correct 278 ms 10568 KB Output is correct
8 Correct 343 ms 10644 KB Output is correct
9 Correct 302 ms 10908 KB Output is correct
10 Correct 244 ms 10676 KB Output is correct
11 Correct 282 ms 10596 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1909 ms 175144 KB Output is correct
3 Correct 3111 ms 176836 KB Output is correct
4 Correct 825 ms 177436 KB Output is correct
5 Correct 3558 ms 207604 KB Output is correct
6 Correct 3013 ms 178132 KB Output is correct
7 Correct 883 ms 44276 KB Output is correct
8 Correct 446 ms 45472 KB Output is correct
9 Correct 925 ms 48812 KB Output is correct
10 Correct 856 ms 45648 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 980 KB Output is correct
2 Correct 294 ms 10584 KB Output is correct
3 Correct 307 ms 10572 KB Output is correct
4 Correct 306 ms 10592 KB Output is correct
5 Correct 327 ms 11000 KB Output is correct
6 Correct 231 ms 10656 KB Output is correct
7 Correct 278 ms 10568 KB Output is correct
8 Correct 343 ms 10644 KB Output is correct
9 Correct 302 ms 10908 KB Output is correct
10 Correct 244 ms 10676 KB Output is correct
11 Correct 282 ms 10596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1909 ms 175144 KB Output is correct
14 Correct 3111 ms 176836 KB Output is correct
15 Correct 825 ms 177436 KB Output is correct
16 Correct 3558 ms 207604 KB Output is correct
17 Correct 3013 ms 178132 KB Output is correct
18 Correct 883 ms 44276 KB Output is correct
19 Correct 446 ms 45472 KB Output is correct
20 Correct 925 ms 48812 KB Output is correct
21 Correct 856 ms 45648 KB Output is correct
22 Correct 2163 ms 176800 KB Output is correct
23 Correct 2297 ms 179056 KB Output is correct
24 Correct 3357 ms 178532 KB Output is correct
25 Correct 3297 ms 182096 KB Output is correct
26 Correct 3298 ms 178660 KB Output is correct
27 Correct 3957 ms 204128 KB Output is correct
28 Correct 1065 ms 181288 KB Output is correct
29 Correct 3268 ms 178340 KB Output is correct
30 Correct 3224 ms 177612 KB Output is correct
31 Correct 3270 ms 178432 KB Output is correct
32 Correct 988 ms 49648 KB Output is correct
33 Correct 490 ms 45552 KB Output is correct
34 Correct 647 ms 42104 KB Output is correct
35 Correct 699 ms 42104 KB Output is correct
36 Correct 867 ms 42584 KB Output is correct
37 Correct 827 ms 42620 KB Output is correct