oj.uz

Submission #545427

# Submission time Handle Problem Language Result Execution time Memory
545427 2022-04-04T13:44:28 Z rainboy Factories (JOI14_factories) C
100 / 100
 3457 ms 228772 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:18:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1048 KB Output is correct
2 Correct 267 ms 19460 KB Output is correct
3 Correct 293 ms 19476 KB Output is correct
4 Correct 295 ms 19432 KB Output is correct
5 Correct 306 ms 19764 KB Output is correct
6 Correct 249 ms 19468 KB Output is correct
7 Correct 280 ms 19496 KB Output is correct
8 Correct 308 ms 19500 KB Output is correct
9 Correct 307 ms 19800 KB Output is correct
10 Correct 222 ms 19500 KB Output is correct
11 Correct 309 ms 19468 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2039 ms 193828 KB Output is correct
3 Correct 3045 ms 194896 KB Output is correct
4 Correct 836 ms 195692 KB Output is correct
5 Correct 3249 ms 226040 KB Output is correct
6 Correct 2699 ms 196824 KB Output is correct
7 Correct 775 ms 57668 KB Output is correct
8 Correct 441 ms 58756 KB Output is correct
9 Correct 864 ms 62296 KB Output is correct
10 Correct 810 ms 59064 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1048 KB Output is correct
2 Correct 267 ms 19460 KB Output is correct
3 Correct 293 ms 19476 KB Output is correct
4 Correct 295 ms 19432 KB Output is correct
5 Correct 306 ms 19764 KB Output is correct
6 Correct 249 ms 19468 KB Output is correct
7 Correct 280 ms 19496 KB Output is correct
8 Correct 308 ms 19500 KB Output is correct
9 Correct 307 ms 19800 KB Output is correct
10 Correct 222 ms 19500 KB Output is correct
11 Correct 309 ms 19468 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2039 ms 193828 KB Output is correct
14 Correct 3045 ms 194896 KB Output is correct
15 Correct 836 ms 195692 KB Output is correct
16 Correct 3249 ms 226040 KB Output is correct
17 Correct 2699 ms 196824 KB Output is correct
18 Correct 775 ms 57668 KB Output is correct
19 Correct 441 ms 58756 KB Output is correct
20 Correct 864 ms 62296 KB Output is correct
21 Correct 810 ms 59064 KB Output is correct
22 Correct 2131 ms 201000 KB Output is correct
23 Correct 2213 ms 203660 KB Output is correct
24 Correct 3126 ms 202820 KB Output is correct
25 Correct 3045 ms 206768 KB Output is correct
26 Correct 2998 ms 203012 KB Output is correct
27 Correct 3457 ms 228772 KB Output is correct
28 Correct 1010 ms 206180 KB Output is correct
29 Correct 2864 ms 202612 KB Output is correct
30 Correct 2897 ms 202080 KB Output is correct
31 Correct 2971 ms 202708 KB Output is correct
32 Correct 899 ms 63280 KB Output is correct
33 Correct 457 ms 59300 KB Output is correct
34 Correct 565 ms 55416 KB Output is correct
35 Correct 592 ms 55424 KB Output is correct
36 Correct 729 ms 55872 KB Output is correct
37 Correct 753 ms 55808 KB Output is correct