oj.uz

Submission #878592

# Submission time Handle Problem Language Result Execution time Memory
878592 2023-11-24T20:43:09 Z rainboy Express 20/19 (ROI19_express) C
15 / 100
 239 ms 115536 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	500000
#define Q	500000
#define K	750	/* (20/19)^K > N*10^11 */

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

int n, p;
int *ej[N]; long long *ew[N]; int eo[N];
long long *lll[N], *rrr[N]; int kk[N];

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

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

void push(int i, int j, long long w) {
	static long long ll[K], rr[K];
	int k, hi, hj;
	long long l, r;

	hi = 0, hj = 0, k = 0;
	while (hi < kk[i] || hj < kk[j]) {
		if (hj == kk[j] || hi < kk[i] && lll[i][hi] + w < lll[j][hj])
			l = lll[i][hi] + w, r = rrr[i][hi] + w, hi++;
		else
			l = lll[j][hj], r = rrr[j][hj], hj++;
		if (k == 0 || (rr[k - 1] + 1) * (p - 1) < l * p)
			ll[k] = l, rr[k] = r, k++;
		else
			rr[k - 1] = max(rr[k - 1], r);
	}
	free(lll[j]), free(rrr[j]);
	lll[j] = (long long *) malloc(k * sizeof *lll[j]);
	rrr[j] = (long long *) malloc(k * sizeof *rrr[j]);
	memcpy(lll[j], ll, k * sizeof *ll), memcpy(rrr[j], rr, k * sizeof *rr), kk[j] = k;
}

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		static char ans[Q + 1];
		int m, q, g, h, i, j, o, lower, upper;
		long long w;

		scanf("%d%d%d%d", &n, &m, &q, &p);
		for (i = 0; i < n; i++) {
			ej[i] = (int *) malloc(2 * sizeof *ej[i]);
			ew[i] = (long long *) malloc(2 * sizeof *ew[i]);
			eo[i] = 0;
		}
		for (h = 0; h < m; h++) {
			scanf("%d%d%lld", &i, &j, &w), i--, j--;
			append(i, j, w);
		}
		memset(kk, 0, n * sizeof *kk);
		for (i = 0; i < n; i++) {
			lll[i] = (long long *) malloc(sizeof *lll[i]);
			rrr[i] = (long long *) malloc(sizeof *rrr[i]);
		}
		lll[0][0] = 0, rrr[0][0] = 0, kk[0] = 1;
		for (i = 0; i < n; i++)
			for (o = eo[i]; o--; ) {
				j = ej[i][o], w = ew[i][o];
				push(i, j, w);
			}
		for (g = 0; g < q; g++) {
			long long d;

			scanf("%d%lld", &i, &d), i--;
			lower = -1, upper = kk[i];
			while (upper - lower > 1) {
				h = (lower + upper) / 2;
				if (rrr[i][h] >= d)
					upper = h;
				else
					lower = h;
			}
			ans[g] = upper < kk[i] && lll[i][upper] * (p - 1) <= d * p ? '1' : '0';
		}
		ans[q] = 0;
		printf("%s\n", ans);
		for (i = 0; i < n; i++) {
			free(ej[i]), free(ew[i]);
			free(lll[i]), free(rrr[i]);
		}
	}
	return 0;
}

Compilation message

express.c: In function 'append':
express.c:18:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
express.c: In function 'push':
express.c:32:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   32 |   if (hj == kk[j] || hi < kk[i] && lll[i][hi] + w < lll[j][hj])
      |                      ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
express.c: In function 'main':
express.c:50:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
express.c:56:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d%d%d%d", &n, &m, &q, &p);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
express.c:63:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |    scanf("%d%d%lld", &i, &j, &w), i--, j--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
express.c:80:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |    scanf("%d%lld", &i, &d), i--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 6 ms 12892 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12736 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 1 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 6 ms 13144 KB Output is correct
13 Correct 6 ms 13144 KB Output is correct
14 Correct 7 ms 12892 KB Output is correct
15 Correct 6 ms 12892 KB Output is correct
16 Correct 6 ms 13032 KB Output is correct
17 Correct 6 ms 12864 KB Output is correct
18 Correct 7 ms 12892 KB Output is correct
19 Correct 6 ms 12892 KB Output is correct
20 Correct 6 ms 12892 KB Output is correct
21 Correct 6 ms 12892 KB Output is correct
22 Correct 6 ms 12892 KB Output is correct
23 Correct 6 ms 12892 KB Output is correct
24 Correct 5 ms 12744 KB Output is correct
25 Correct 5 ms 12636 KB Output is correct
26 Correct 5 ms 12636 KB Output is correct
27 Correct 5 ms 12636 KB Output is correct
28 Correct 5 ms 12636 KB Output is correct
29 Correct 5 ms 12636 KB Output is correct
30 Correct 5 ms 12636 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12724 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12728 KB Output is correct
5 Correct 1 ms 12636 KB Output is correct
6 Correct 1 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 4 ms 12976 KB Output is correct
11 Runtime error 16 ms 28956 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Runtime error 239 ms 115536 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Runtime error 239 ms 115536 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Runtime error 15 ms 26680 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Runtime error 15 ms 26680 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 6 ms 12892 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12736 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 1 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 6 ms 13144 KB Output is correct
13 Correct 6 ms 13144 KB Output is correct
14 Correct 7 ms 12892 KB Output is correct
15 Correct 6 ms 12892 KB Output is correct
16 Correct 6 ms 13032 KB Output is correct
17 Correct 6 ms 12864 KB Output is correct
18 Correct 7 ms 12892 KB Output is correct
19 Correct 6 ms 12892 KB Output is correct
20 Correct 6 ms 12892 KB Output is correct
21 Correct 6 ms 12892 KB Output is correct
22 Correct 6 ms 12892 KB Output is correct
23 Correct 6 ms 12892 KB Output is correct
24 Correct 5 ms 12744 KB Output is correct
25 Correct 5 ms 12636 KB Output is correct
26 Correct 5 ms 12636 KB Output is correct
27 Correct 5 ms 12636 KB Output is correct
28 Correct 5 ms 12636 KB Output is correct
29 Correct 5 ms 12636 KB Output is correct
30 Correct 5 ms 12636 KB Output is correct
31 Correct 2 ms 12724 KB Output is correct
32 Correct 2 ms 12636 KB Output is correct
33 Correct 2 ms 12636 KB Output is correct
34 Correct 2 ms 12728 KB Output is correct
35 Correct 1 ms 12636 KB Output is correct
36 Correct 1 ms 12636 KB Output is correct
37 Correct 2 ms 12636 KB Output is correct
38 Correct 2 ms 12636 KB Output is correct
39 Correct 1 ms 12636 KB Output is correct
40 Correct 4 ms 12976 KB Output is correct
41 Runtime error 16 ms 28956 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -