oj.uz

Submission #745239

# Submission time Handle Problem Language Result Execution time Memory
745239 2023-05-19T15:20:53 Z rainboy Roadside Advertisements (NOI17_roadsideadverts) C
100 / 100
 91 ms 11340 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	50000
#define M	5

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *ej[N], *ew[N], eo[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 dd[N], pp[N], qq[N], xx[N];

int dfs1(int p, int i, int d, int x) {
	int o, s, k_, j_;

	pp[i] = p, dd[i] = d, xx[i] = x;
	s = 1, k_ = 0, j_ = -1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o], w = ew[i][o];

		if (j != p) {
			int k = dfs1(i, j, d + 1, x + w);

			s += k;
			if (k_ < k)
				k_ = k, j_ = j;
		}
	}
	qq[i] = j_;
	return s;
}

int ta[N], tb[N];

void dfs2(int p, int i, int q) {
	static int time;
	int o, j_;

	ta[i] = time++;
	j_ = qq[i], qq[i] = q;
	if (j_ != -1)
		dfs2(i, j_, q);
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p && j != j_)
			dfs2(i, j, j);
	}
	tb[i] = time;
}

int lca(int i, int j) {
	while (qq[i] != qq[j])
		if (dd[qq[i]] > dd[qq[j]])
			i = pp[qq[i]];
		else
			j = pp[qq[j]];
	return dd[i] < dd[j] ? i : j;
}

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (ta[ii[j]] == ta[i_])
				j++;
			else if (ta[ii[j]] < ta[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

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

	scanf("%d", &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++) {
		scanf("%d%d%d", &i, &j, &w);
		append(i, j, w), append(j, i, w);
	}
	dfs1(-1, 0, 0, 0);
	dfs2(-1, 0, 0);
	scanf("%d", &q);
	while (q--) {
		static int ii[M];
		int ans;

		for (h = 0; h < M; h++)
			scanf("%d", &ii[h]);
		sort(ii, 0, M);
		ans = 0;
		for (h = 0; h < M; h++)
			ans += xx[ii[h]];
		for (h = 0; h < M; h++)
			ans -= xx[lca(ii[h], ii[(h + 1) % M])];
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message

roadsideadverts.c: In function 'append':
roadsideadverts.c:18:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
roadsideadverts.c: In function 'main':
roadsideadverts.c:97:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
roadsideadverts.c:103:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf("%d%d%d", &i, &j, &w);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.c:108:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
roadsideadverts.c:114:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |    scanf("%d", &ii[h]);
      |    ^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 9104 KB Output is correct
2 Correct 41 ms 11280 KB Output is correct
3 Correct 41 ms 11340 KB Output is correct
4 Correct 40 ms 11268 KB Output is correct
5 Correct 41 ms 11252 KB Output is correct
6 Correct 44 ms 11328 KB Output is correct
7 Correct 41 ms 11260 KB Output is correct
8 Correct 47 ms 11276 KB Output is correct
9 Correct 41 ms 11268 KB Output is correct
10 Correct 50 ms 11284 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6456 KB Output is correct
2 Correct 34 ms 10016 KB Output is correct
3 Correct 36 ms 10044 KB Output is correct
4 Correct 91 ms 10044 KB Output is correct
5 Correct 33 ms 10008 KB Output is correct
6 Correct 30 ms 10060 KB Output is correct
7 Correct 27 ms 10008 KB Output is correct
8 Correct 30 ms 9960 KB Output is correct
9 Correct 28 ms 9948 KB Output is correct
10 Correct 47 ms 10000 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 41 ms 9104 KB Output is correct
3 Correct 41 ms 11280 KB Output is correct
4 Correct 41 ms 11340 KB Output is correct
5 Correct 40 ms 11268 KB Output is correct
6 Correct 41 ms 11252 KB Output is correct
7 Correct 44 ms 11328 KB Output is correct
8 Correct 41 ms 11260 KB Output is correct
9 Correct 47 ms 11276 KB Output is correct
10 Correct 41 ms 11268 KB Output is correct
11 Correct 50 ms 11284 KB Output is correct
12 Correct 30 ms 6456 KB Output is correct
13 Correct 34 ms 10016 KB Output is correct
14 Correct 36 ms 10044 KB Output is correct
15 Correct 91 ms 10044 KB Output is correct
16 Correct 33 ms 10008 KB Output is correct
17 Correct 30 ms 10060 KB Output is correct
18 Correct 27 ms 10008 KB Output is correct
19 Correct 30 ms 9960 KB Output is correct
20 Correct 28 ms 9948 KB Output is correct
21 Correct 47 ms 10000 KB Output is correct
22 Correct 41 ms 9036 KB Output is correct
23 Correct 40 ms 6780 KB Output is correct
24 Correct 38 ms 10444 KB Output is correct
25 Correct 43 ms 10332 KB Output is correct
26 Correct 41 ms 10380 KB Output is correct
27 Correct 42 ms 10316 KB Output is correct
28 Correct 51 ms 10416 KB Output is correct
29 Correct 48 ms 10436 KB Output is correct
30 Correct 45 ms 10312 KB Output is correct
31 Correct 45 ms 10332 KB Output is correct