Submission #544759

#	Time	Username	Problem	Language	Result	Execution time	Memory
544759		rainboy	From Hacks to Snitches (BOI21_watchmen)	C11	100 / 100	2825 ms	145004 KiB

watchmen

/* upsolve after reading spoiler */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define N	250000
#define M	3000000
#define K	2750
#define L	1500
#define N_	(N + K * L) 
#define INF	0x3f3f3f3f
 
int min(int a, int b) { return a < b ? a : b; }
 
int dd[N_], pq[N_], iq[1 + 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 *ej[N], eo[N];
 
void append(int i, int j) {
	ej[i][eo[i]++] = j;
}
 
void update(int i, int d) {
	if (dd[i] > d) {
		if (dd[i] == INF)
			pq_add_last(i);
		dd[i] = d, pq_up(i);
	}
}
 
int main() {
	static int uu[M], vv[M], gg[N], hh[N], ll[K], ii[K][L], iil[N], iir[N], idx[N_];
	int n, n_, m, k, g, g_, h, i, j;
 
	scanf("%d%d", &n, &m);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &uu[h], &vv[h]), uu[h]--, vv[h]--;
		eo[uu[h]]++, eo[vv[h]]++;
	}
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(eo[i] * sizeof *ej[i]), eo[i] = 0;
	for (h = 0; h < m; h++)
		append(uu[h], vv[h]), append(vv[h], uu[h]);
	scanf("%d", &k);
	memset(gg, -1, n * sizeof *gg);
	for (g = 0; g < k; g++) {
		scanf("%d", &ll[g]);
		for (h = 0; h < ll[g]; h++) {
			scanf("%d", &i), i--;
			ii[g][h] = i;
			gg[i] = g, hh[i] = h;
		}
	}
	n_ = 0;
	for (i = 0, n_ = 0; i < n; i++) {
		if (gg[i] == -1)
			iil[i] = n_, iir[i] = n_ + 1;
		else
			iil[i] = n_, iir[i] = n_ + ll[gg[i]];
		while (n_ < iir[i])
			idx[n_++] = i;
	}
	memset(dd, 0x3f, n_ * sizeof *dd);
	dd[0] = 0, pq_add_last(0);
	while (cnt) {
		int i_, d, d_, d1, p, q, o, o_;
 
		i_ = pq_remove_first(), i = idx[i_], g = gg[i], h = hh[i], d = dd[i_];
		if (i == n - 1) {
			printf("%d\n", d);
			return 0;
		}
		if (g == -1) {
			for (o = eo[i]; o--; ) {
				j = ej[i][o], g_ = gg[j];
				if (g_ == -1)
					update(iil[j], d + 1);
				else {
					d_ = (d - hh[j] + ll[g_]) / ll[g_] * ll[g_] + hh[j];
					if ((d + 1) % ll[g_] != hh[j])
						update(iil[j] + (d + 1) % ll[g_], d + 1);
					update(iil[j] + (d_ + 1) % ll[g_], d_ + 1);
				}
			}
		} else {
			if ((d + 1) % ll[g] != h)
				update(iil[i] + (d + 1) % ll[g], d + 1);
			p = ii[g][(h - 1 + ll[g]) % ll[g]], q = ii[g][(h + 1) % ll[g]];
			for (o = 0, o_ = 0; o < eo[i]; o++) {
				j = ej[i][o], g_ = gg[j];
				if (g_ == -1)
					update(iil[j], d + 1);
				else if (j == q) {
					update(iil[j] + (d + 1) % ll[g_], d + 1);
					ej[i][o_++] = j;
				} else if (j == p) {
					if ((d + 1) % ll[g_] != hh[j] && (d + 1) % ll[g_] != h)
						update(iil[j] + (d + 1) % ll[g_], d + 1);
					ej[i][o_++] = j;
				} else {
					d_ = (d - hh[j] + ll[g_]) / ll[g_] * ll[g_] + hh[j];
					if ((d + 1) % ll[g_] != hh[j])
						update(iil[j] + (d + 1) % ll[g_], d + 1);
					if (d_ % ll[g] == h) {
						d1 = d + (d_ - d + ll[g]) / ll[g] * ll[g];
						d_ = (d1 - hh[j] + ll[g_]) / ll[g_] * ll[g_] + hh[j];
						if ((d1 + 1) % ll[g_] != hh[j])
							update(iil[j] + (d1 + 1) % ll[g_], d1 + 1);
						ej[i][o_++] = j;
					}
					if (d_ % ll[g] != h)
						update(iil[j] + (d_ + 1) % ll[g_], d_ + 1);
				}
			}
			eo[i] = o_;
		}
	}
	printf("impossible\n");
	return 0;
}

Compilation message (stderr)

watchmen.c: In function 'main':
watchmen.c:70:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
watchmen.c:72:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d%d", &uu[h], &vv[h]), uu[h]--, vv[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watchmen.c:79:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%d", &k);
      |  ^~~~~~~~~~~~~~~
watchmen.c:82:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d", &ll[g]);
      |   ^~~~~~~~~~~~~~~~~~~
watchmen.c:84:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 25 / 25
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20