Submission #882159

#	Time	Username	Problem	Language	Result	Execution time	Memory
882159		rainboy	Shell (info1cup18_shell)	C11	100 / 100	200 ms	37756 KiB

shell

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

#define N	1000000
#define MD	1000000007

int *ej[N], eo[N], in[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int main() {
	static int ii[N], qu[N], hh[N], dp[N];
	int n, m, k, cnt, g, h, i, j, s, t, o, ans;

	scanf("%d%d%d", &n, &m, &k);
	for (g = 0; g < k; g++)
		scanf("%d", &ii[g]), ii[g]--;
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	while (m--) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), in[j]++;
	}
	cnt = 0;
	for (i = 0; i < n; i++)
		if (in[i] == 0)
			qu[hh[i] = cnt++] = i;
	for (h = 0; h < cnt; h++) {
		i = qu[h];
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (--in[j] == 0)
				qu[hh[j] = cnt++] = j;
		}
	}
	ans = 1;
	for (g = -1; g < k; g++) {
		s = g < 0 ? 0 : ii[g], t = g + 1 == k ? n - 1 : ii[g + 1];
		if (hh[s] > hh[t]) {
			ans = 0;
			break;
		}
		dp[s] = 1;
		for (h = hh[s]; h < hh[t]; h++) {
			i = qu[h];
			for (o = eo[i]; o--; ) {
				j = ej[i][o];
				if (hh[j] <= hh[t])
					dp[j] = (dp[j] + dp[i]) % MD;
			}
		}
		ans = (long long) ans * dp[t] % MD;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 45 / 45
• Subtask 3: 20 / 20
• Subtask 4: 25 / 25