oj.uz

Submission #708039

# Submission time Handle Problem Language Result Execution time Memory
708039 2023-03-10T20:58:05 Z rainboy Robot (JOI21_ho_t4) C
100 / 100
 992 ms 147964 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	200000
#define M	200000
#define N_	(N + M * 6)
#define INF	0x3f3f3f3f3f3f3f3f

unsigned int X = 12345;

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

int ij[M * 2], cc[M], ww[M], m;
int *eh[N], eo[N], n;
int *ej[N_], eo_[N_], n_; long long *ew[N_];

int newnode() {
	int i = n_++;

	ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	ew[i] = (long long *) malloc(2 * sizeof *ew[i]);
	return i;
}

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;
}

void append_(int i, int j, long long 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] = (long long *) realloc(ew[i], o * 2 * sizeof *ew[i]);
	}
	ej[i][o] = j, ew[i][o] = w;
}

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

		while (j < k)
			if (cc[hh[j] >> 1] == cc[h >> 1])
				j++;
			else if (cc[hh[j] >> 1] < cc[h >> 1]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

void add_edges(int *hh, int m, int i) {
	static int uu[M], vv[M];
	static long long pp[M], qq[M];
	int h, h_, j;
	long long sum;

	for (h = 0; h < m; h++) {
		uu[h] = newnode();
		vv[h] = newnode();
	}
	sum = 0;
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		sum += ww[h_ >> 1];
	}
	for (h = 0; h < m; h++) {
		h_ = hh[h], j = ij[h_ ^ 1];
		append_(i, j, sum - ww[h_ >> 1]);
		append_(i, n + h_, ww[h_ >> 1]);
	}
	pp[0] = 0;
	for (h = 0; h + 1 < m; h++) {
		h_ = hh[h];
		pp[h + 1] = pp[h] + ww[h_ >> 1];
	}
	qq[m - 1] = 0;
	for (h = m - 1; h > 0; h--) {
		h_ = hh[h];
		qq[h - 1] = qq[h] + ww[h_ >> 1];
	}
	for (h = 0; h < m; h++) {
		h_ = hh[h], j = ij[h_ ^ 1];
		append_(n + (h_ ^ 1), i, 0);
		if (h + 1 < m)
			append_(n + (h_ ^ 1), uu[h + 1], pp[h]);
		if (h > 0)
			append_(n + (h_ ^ 1), vv[h - 1], qq[h]);
		append_(uu[h], j, qq[h]), append_(vv[h], j, pp[h]);
	}
	for (h = 0; h + 1 < m; h++) {
		h_ = hh[h];
		append_(uu[h], uu[h + 1], ww[h_ >> 1]);
	}
	for (h = m - 1; h > 0; h--) {
		h_ = hh[h];
		append_(vv[h], vv[h - 1], ww[h_ >> 1]);
	}
}

long long dd[N_]; int iq[N_ + 1], pq[N_], cnt;

int lt(int i, int j) { return dd[i] < dd[j]; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add_last(int i) {
	iq[pq[i] = ++cnt] = i;
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];

	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

int main() {
	int h, i, j, c, o, o_;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d%d%d", &i, &j, &c, &ww[h]), i--, j--, c--;
		ij[h << 1 | 0] = i, ij[h << 1 | 1] = j, cc[h] = c;
		append(i, h << 1 | 0), append(j, h << 1 | 1);
	}
	for (i = 0; i < n + m * 2; i++)
		newnode();
	for (i = 0; i < n; i++) {
		sort(eh[i], 0, eo[i]);
		for (o = 0; o < eo[i]; o = o_) {
			o_ = o + 1, c = cc[eh[i][o] >> 1];
			while (o_ < eo[i] && cc[eh[i][o_] >> 1] == c)
				o_++;
			add_edges(eh[i] + o, o_ - o, i);
		}
	}
	memset(dd, 0x3f, n_ * sizeof *dd);
	dd[0] = 0, pq_add_last(0);
	while (cnt) {
		i = pq_remove_first();
		if (i == n - 1) {
			printf("%lld\n", dd[i]);
			return 0;
		}
		for (o = eo_[i]; o--; ) {
			long long w, d;

			j = ej[i][o], w = ew[i][o], d = dd[i] + w;
			if (dd[j] > d) {
				if (dd[j] == INF)
					pq_add_last(j);
				dd[j] = d, pq_up(j);
			}
		}
	}
	printf("-1\n");
	return 0;
}

Compilation message

Main.c: In function 'append':
Main.c:31:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   31 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'append_':
Main.c:39:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   39 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
Main.c: In function 'main':
Main.c:154:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:158:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |   scanf("%d%d%d%d", &i, &j, &c, &ww[h]), i--, j--, c--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 2 ms 928 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 3 ms 1712 KB Output is correct
10 Correct 4 ms 1848 KB Output is correct
11 Correct 4 ms 1748 KB Output is correct
12 Correct 4 ms 1620 KB Output is correct
13 Correct 5 ms 1748 KB Output is correct
14 Correct 4 ms 1748 KB Output is correct
15 Correct 3 ms 1076 KB Output is correct
16 Correct 5 ms 1748 KB Output is correct
17 Correct 3 ms 1364 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 4 ms 1748 KB Output is correct
20 Correct 3 ms 1332 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 55428 KB Output is correct
2 Correct 95 ms 24560 KB Output is correct
3 Correct 272 ms 91916 KB Output is correct
4 Correct 87 ms 37168 KB Output is correct
5 Correct 610 ms 137384 KB Output is correct
6 Correct 618 ms 139416 KB Output is correct
7 Correct 456 ms 143004 KB Output is correct
8 Correct 622 ms 142380 KB Output is correct
9 Correct 654 ms 142416 KB Output is correct
10 Correct 341 ms 84272 KB Output is correct
11 Correct 142 ms 71012 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 2 ms 928 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 3 ms 1712 KB Output is correct
10 Correct 4 ms 1848 KB Output is correct
11 Correct 4 ms 1748 KB Output is correct
12 Correct 4 ms 1620 KB Output is correct
13 Correct 5 ms 1748 KB Output is correct
14 Correct 4 ms 1748 KB Output is correct
15 Correct 3 ms 1076 KB Output is correct
16 Correct 5 ms 1748 KB Output is correct
17 Correct 3 ms 1364 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 4 ms 1748 KB Output is correct
20 Correct 3 ms 1332 KB Output is correct
21 Correct 171 ms 55428 KB Output is correct
22 Correct 95 ms 24560 KB Output is correct
23 Correct 272 ms 91916 KB Output is correct
24 Correct 87 ms 37168 KB Output is correct
25 Correct 610 ms 137384 KB Output is correct
26 Correct 618 ms 139416 KB Output is correct
27 Correct 456 ms 143004 KB Output is correct
28 Correct 622 ms 142380 KB Output is correct
29 Correct 654 ms 142416 KB Output is correct
30 Correct 341 ms 84272 KB Output is correct
31 Correct 142 ms 71012 KB Output is correct
32 Correct 250 ms 104852 KB Output is correct
33 Correct 236 ms 82512 KB Output is correct
34 Correct 272 ms 100104 KB Output is correct
35 Correct 233 ms 83424 KB Output is correct
36 Correct 396 ms 94568 KB Output is correct
37 Correct 641 ms 123888 KB Output is correct
38 Correct 705 ms 147728 KB Output is correct
39 Correct 874 ms 132208 KB Output is correct
40 Correct 685 ms 147696 KB Output is correct
41 Correct 850 ms 147964 KB Output is correct
42 Correct 939 ms 130144 KB Output is correct
43 Correct 323 ms 68172 KB Output is correct
44 Correct 371 ms 142768 KB Output is correct
45 Correct 612 ms 112592 KB Output is correct
46 Correct 438 ms 100724 KB Output is correct
47 Correct 799 ms 112444 KB Output is correct
48 Correct 992 ms 142992 KB Output is correct