Submission #878593

#	Time	Username	Problem	Language	Result	Execution time	Memory
878593		rainboy	Express 20/19 (ROI19_express)	C11	100 / 100	552 ms	231728 KiB

express

#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;

	k = 0, hi = 0, hj = 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 < l * (p - 1))
			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 (stderr)

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 / 15
• Subtask 2: 24 / 24
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11