oj.uz

Submission #882159

# Submission time Handle Problem Language Result Execution time Memory
882159 2023-12-02T17:42:09 Z rainboy Shell (info1cup18_shell) C
100 / 100
 200 ms 37756 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 4 ms 10944 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 6 ms 11100 KB Output is correct
10 Correct 5 ms 11096 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 69 ms 17768 KB Output is correct
3 Correct 66 ms 17672 KB Output is correct
4 Correct 61 ms 17604 KB Output is correct
5 Correct 39 ms 15192 KB Output is correct
6 Correct 138 ms 27664 KB Output is correct
7 Correct 144 ms 27820 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 4 ms 10944 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 6 ms 11100 KB Output is correct
10 Correct 5 ms 11096 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 69 ms 17768 KB Output is correct
13 Correct 66 ms 17672 KB Output is correct
14 Correct 61 ms 17604 KB Output is correct
15 Correct 39 ms 15192 KB Output is correct
16 Correct 138 ms 27664 KB Output is correct
17 Correct 144 ms 27820 KB Output is correct
18 Correct 200 ms 37756 KB Output is correct
19 Correct 191 ms 36692 KB Output is correct
20 Correct 191 ms 36436 KB Output is correct
21 Correct 74 ms 18984 KB Output is correct
22 Correct 187 ms 37204 KB Output is correct