Submission #680449

#	Time	Username	Problem	Language	Result	Execution time	Memory
680449		rainboy	Wild Boar (JOI18_wild_boar)	C11	0 / 100	1 ms	596 KiB

wild_boar

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

#define N	2000
#define M	2000
#define M2	(M * 2)
#define MM	(M * M)
#define K	6
#define L	100000
#define N_	(1 << 17)	/* N_ = pow2(ceil(log2(L))) */
#define INF	0x3f3f3f3f3f3f3f3fLL

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

unsigned int Z = 12345;

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

int ij[M2], cc[M], m;
int *eh[N], eo[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[M2 + 1], pq[M2], 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 solve(long long *dd, int u) {
	static int kk[N];
	int h, i, o;

	memset(dd, 0x3f, m * 2 * sizeof *dd), memset(kk, 0, n * sizeof *kk);
	dd_ = dd, dd[u] = cc[u >> 1], pq_add_last(u);
	while (cnt) {
		h = pq_remove_first(), i = ij[h ^ 1];
		if (kk[i] < 2) {
			kk[i]++;
			for (o = eo[i]; o--; ) {
				int h_ = eh[i][o];
				long long d = dd[h] + cc[h_ >> 1];

				if ((h ^ h_) != 1 && dd[h_] > d) {
					if (dd[h_] == INF)
						pq_add_last(h_);
					dd[h_] = d, pq_up(h_);
				}
			}
		}
	}
}

int uu1[MM], vv1[MM]; long long ww1[MM];

int compare_uv(int h1, int h2) {
	return uu1[h1] != uu1[h2] ? uu1[h1] - uu1[h2] : vv1[h1] - vv1[h2];
}

int compare_w(int h1, int h2) {
	return ww1[h1] == ww1[h2] ? 0 : (ww1[h1] < ww1[h2] ? -1 : 1);
}

int (*compare)(int, int);

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

		while (j < k) {
			int c = compare(gg[j], g);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = gg[i], gg[i] = gg[j], gg[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = gg[j], gg[j] = gg[k], gg[k] = tmp;
			}
		}
		sort(gg, l, i);
		l = k;
	}
}

int simplify(int k) {
	static int dd1[M2], dd2[M2], gg[MM], uu_[MM], vv_[MM];
	static long long ww_[MM];
	int k_, g, g_, u, v;
	long long w;

	for (g = 0; g < k; g++)
		gg[g] = g;
	compare = compare_uv, sort(gg, 0, k);
	k_ = 0;
	for (g = 0; g < k; g++) {
		u = uu1[gg[g]], v = vv1[gg[g]];
		g_ = g, w = INF;
		while (g_ < k && uu1[gg[g_]] == u && vv1[gg[g_]] == v)
			w = min(w, ww1[gg[g_++]]);
		uu_[k_] = u, vv_[k_] = v, ww_[k_] = w, k_++;
	}
	memcpy(uu1, uu_, k_ * sizeof *uu_);
	memcpy(vv1, vv_, k_ * sizeof *vv_);
	memcpy(ww1, ww_, k_ * sizeof *ww_);
	k = k_;
	for (g = 0; g < k; g++)
		gg[g] = g;
	compare = compare_w, sort(gg, 0, k);
	k_ = 0;
	for (g = 0; g < k; g++) {
		g_ = gg[g], u = uu1[g_], v = vv1[g_], w = ww1[g_];
		if (dd1[u] >= 2 || dd2[v] >= 2)
			continue;
		dd1[u]++, dd2[v]++;
		if (k_ < K)
			uu_[k_] = u, vv_[k_] = v, ww_[k_] = w, k_++;
	}
	for (g = 0; g < k; g++) {
		u = uu1[g], v = vv1[g];
		dd1[u] = 0, dd2[v] = 0;
	}
	memcpy(uu1, uu_, k_ * sizeof *uu_);
	memcpy(vv1, vv_, k_ * sizeof *vv_);
	memcpy(ww1, ww_, k_ * sizeof *ww_);
	return k_;
}

int uu[N][N][K], vv[N][N][K], kk[N][N]; long long ww[N][N][K];

int uu_[N_ * 2][K], vv_[N_ * 2][K], kk_[N_ * 2], n_; long long ww_[N_ * 2][K];

void pul(int i) {
	int l, r, k, g1, g2;

	l = i << 1, r = l | 1;
	if (kk_[l] == -1 && kk_[r] == -1)
		kk_[i] = -1;
	else if (kk_[r] == -1) {
		memcpy(uu_[i], uu_[l], kk_[l] * sizeof *uu_[l]);
		memcpy(vv_[i], vv_[l], kk_[l] * sizeof *vv_[l]);
		memcpy(ww_[i], ww_[l], kk_[l] * sizeof *ww_[l]);
		kk_[i] = kk_[l];
	} else if (kk_[l] == -1) {
		memcpy(uu_[i], uu_[r], kk_[r] * sizeof *uu_[r]);
		memcpy(vv_[i], vv_[r], kk_[r] * sizeof *vv_[r]);
		memcpy(ww_[i], ww_[r], kk_[r] * sizeof *ww_[r]);
		kk_[i] = kk_[r];
	} else {
		k = 0;
		for (g1 = 0; g1 < kk_[l]; g1++)
			for (g2 = 0; g2 < kk_[r]; g2++)
				if ((vv_[l][g1] ^ uu_[r][g2]) != 1)
					uu1[k] = uu_[l][g1], vv1[k] = vv_[r][g2], ww1[k] = min(ww_[l][g1] + ww_[r][g2], INF), k++;
		k = simplify(k);
		memcpy(uu_[i], uu1, k * sizeof *uu1);
		memcpy(vv_[i], vv1, k * sizeof *vv1);
		memcpy(ww_[i], ww1, k * sizeof *ww1);
		kk_[i] = k;
	}
}

int ii[L], l;

void build() {
	int h, i, j;

	n_ = 1;
	while (n_ < l)
		n_ <<= 1;
	for (h = 0; h < n_; h++)
		if (h + 1 < l) {
			i = ii[h], j = ii[h + 1];
			memcpy(uu_[n_ + h], uu[i][j], kk[i][j] * sizeof *uu[i][j]);
			memcpy(vv_[n_ + h], vv[i][j], kk[i][j] * sizeof *vv[i][j]);
			memcpy(ww_[n_ + h], ww[i][j], kk[i][j] * sizeof *ww[i][j]);
			kk_[n_ + h] = kk[i][j];
		} else
			kk_[n_ + h] = -1;
	for (h = n_ - 1; h > 0; h--)
		pul(h);
}

void upd(int h) {
	int i = ii[h], j = ii[h + 1];

	memcpy(uu_[n_ + h], uu[i][j], kk[i][j] * sizeof *uu[i][j]);
	memcpy(vv_[n_ + h], vv[i][j], kk[i][j] * sizeof *vv[i][j]);
	memcpy(ww_[n_ + h], ww[i][j], kk[i][j] * sizeof *ww[i][j]);
	kk_[n_ + h] = kk[i][j];
	h += n_;
	while (h > 1)
		pul(h >>= 1);
}

int main() {
	static long long dd[M2][M2];
	int q, k, g, h, i, j, u, v, o, o_;

	scanf("%d%d%d%d", &n, &m, &q, &l);
	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, &cc[h]), i--, j--;
		ij[h << 1 | 0] = i, ij[h << 1 | 1] = j;
		append(i, h << 1 | 0), append(j, h << 1 | 1);
	}
	for (u = 0; u < m * 2; u++)
		solve(dd[u], u);
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++) {
			k = 0;
			for (o = eo[i]; o--; ) {
				u = eh[i][o];
				for (o_ = eo[j]; o_--; ) {
					v = eh[j][o_] ^ 1;
					uu1[k] = u, vv1[k] = v, ww1[k] = dd[u][v], k++;
				}
			}
			k = simplify(k);
			memcpy(uu[i][j], uu1, k * sizeof *uu1);
			memcpy(vv[i][j], vv1, k * sizeof *vv1);
			memcpy(ww[i][j], ww1, k * sizeof *ww1);
			kk[i][j] = k;
		}
	for (h = 0; h < l; h++)
		scanf("%d", &ii[h]), ii[h]--;
	build();
	while (q--) {
		long long ans;

		scanf("%d%d", &h, &i), h--, i--;
		ii[h] = i;
		if (h > 0)
			upd(h - 1);
		if (h + 1 < l)
			upd(h);
		ans = INF;
		for (g = 0; g < kk_[1]; g++)
			ans = min(ans, ww_[1][g]);
		printf("%lld\n", ans == INF ? -1 : ans);
	}
	return 0;
}

Compilation message (stderr)

wild_boar.c: In function 'append':
wild_boar.c:28:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   28 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
wild_boar.c: In function 'main':
wild_boar.c:242:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  242 |  scanf("%d%d%d%d", &n, &m, &q, &l);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.c:246:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  246 |   scanf("%d%d%d", &i, &j, &cc[h]), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.c:269:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  269 |   scanf("%d", &ii[h]), ii[h]--;
      |   ^~~~~~~~~~~~~~~~~~~
wild_boar.c:274:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  274 |   scanf("%d%d", &h, &i), h--, i--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38