Submission #949001

#	Time	Username	Problem	Language	Result	Execution time	Memory
949001		rainboy	Tales of seafaring (POI13_mor)	C11	100 / 100	1020 ms	34704 KiB

mor

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

#define N	5000
#define M	5000
#define Q	1000000
#define INF	0x3f3f3f3f

void append(int **ej, int *eo, 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 *ej[N], eo[N], *eh[N], eo_[N], tt[Q], cc[Q], dd[N * 2], qu[N * 2];
	static char tak[Q];
	int n, m, q, cnt, g, h, i, i_, j, j_, s, u, o, d;

	scanf("%d%d%d", &n, &m, &q);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(ej, eo, i, j), append(ej, eo, j, i);
	}
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < q; h++) {
		scanf("%d%d%d", &i, &tt[h], &cc[h]), i--, tt[h]--;
		append(eh, eo_, i, h);
	}
	for (s = 0; s < n; s++) {
		memset(dd, 0x3f, n * 2 * sizeof *dd);
		cnt = 0;
		dd[s << 1 | 0] = 0, qu[cnt++] = s << 1 | 0;
		for (g = 0; g < cnt; g++) {
			i_ = qu[g], i = i_ >> 1, u = i_ & 1, d = dd[i_] + 1;
			for (o = eo[i]; o--; ) {
				j = ej[i][o], j_ = j << 1 | u ^ 1;
				if (dd[j_] > d)
					dd[j_] = d, qu[cnt++] = j_;
			}
		}
		if (eo[s])
			for (o = eo_[s]; o--; ) {
				h = eh[s][o];
				tak[h] = dd[tt[h] << 1 | cc[h] & 1] <= cc[h];
			}
	}
	for (h = 0; h < q; h++)
		printf(tak[h] ? "TAK\n" : "NIE\n");
	return 0;
}

Compilation message (stderr)

mor.c: In function 'append':
mor.c:13:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   13 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
mor.c: In function 'main':
mor.c:43:35: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   43 |     j = ej[i][o], j_ = j << 1 | u ^ 1;
      |                                 ~~^~~
mor.c:51:36: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   51 |     tak[h] = dd[tt[h] << 1 | cc[h] & 1] <= cc[h];
      |                              ~~~~~~^~~
mor.c:23:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
mor.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--;
      |   ^~~~~~~~~~~~~~~~~~~~~
mor.c:33:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d%d%d", &i, &tt[h], &cc[h]), i--, tt[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10