Submission #834127

#	Time	Username	Problem	Language	Result	Execution time	Memory
834127		rainboy	Aesthetic (NOI20_aesthetic)	C11	100 / 100	383 ms	29644 KiB

Aesthetic

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

#define N	300000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N))) */
#define M	300000
#define INF	0x3f3f3f3f3f3f3f3fLL

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

int ii[M], jj[M], ww[M]; char path[M]; int m;
int *eh[N], eo[N]; long long dds[N], ddt[N]; int ff[N], gg[N], n;

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

long long *dd; 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;
}

void dijkstra(int n, int s) {
	int i, o;

	memset(dd, 0x3f, n * sizeof *dd);
	memset(pq, 0, n * sizeof *pq), cnt = 0;
	dd[s] = 0, ff[s] = -1, pq_add_last(s);
	while (cnt) {
		i = pq_remove_first();
		for (o = eo[i]; o--; ) {
			int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
			long long d = dd[i] + ww[h];

			if (dd[j] > d) {
				if (dd[j] == INF)
					pq_add_last(j);
				dd[j] = d, ff[j] = h, pq_up(j);
			}
		}
	}
}

void dfs(int i, int g) {
	int o;

	gg[i] = g;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
		long long d = dds[i] + ww[h];

		if (dds[j] == d && gg[j] == -1)
			dfs(j, g);
	}
}

long long st[N_ * 2]; int n_;

void update(int l, int r, long long x) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			st[l] = min(st[l], x), l++;
		if ((r & 1) == 0)
			st[r] = min(st[r], x), r--;
	}
}

int main() {
	static int qu[N];
	int g, h, i, j, l, r, tmp, w;
	long long ans;

	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", &i, &j, &ww[h]), i--, j--;
		ii[h] = i, jj[h] = j;
		append(i, h), append(j, h);
	}
	dd = dds, dijkstra(n, 0);
	dd = ddt, dijkstra(n, n - 1);
	i = 0, cnt = 0;
	while (i != n - 1) {
		qu[cnt++] = i;
		h = ff[i];
		path[h] = 1, i ^= ii[h] ^ jj[h];
	}
	qu[cnt++] = i;
	memset(gg, -1, n * sizeof *gg);
	for (g = 0; g < cnt; g++)
		gg[qu[g]] = g;
	for (g = 0; g < cnt; g++)
		dfs(qu[g], g);
	n_ = 1;
	while (n_ < cnt)
		n_ <<= 1;
	memset(st, 0x3f, n_ * 2 * sizeof *st);
	for (h = 0; h < m; h++)
		if (!path[h]) {
			i = ii[h], j = jj[h], l = gg[i], r = gg[j];
			if (l > r)
				tmp = i, i = j, j = tmp, tmp = l, l = r, r = tmp;
			if (l < r)
				update(l, r - 1, dds[i] + ww[h] + ddt[j]);
		}
	for (i = 1; i < n_; i++) {
		st[i << 1 | 0] = min(st[i << 1 | 0], st[i]);
		st[i << 1 | 1] = min(st[i << 1 | 1], st[i]);
	}
	w = 0, ans = dds[n - 1];
	for (h = m - 1; h >= 0; h--) {
		if (path[h]) {
			g = min(gg[ii[h]], gg[jj[h]]);
			ans = max(ans, min(dds[n - 1] + w, st[n_ + g]));
		}
		w = max(w, ww[h]);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22
• Subtask 7: 27 / 27