oj.uz

답안 #949001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
949001 2024-03-18T19:02:50 Z rainboy Tales of seafaring (POI13_mor) C
100 / 100
 1020 ms 34704 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 220 ms 34704 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2472 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 222 ms 34460 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2564 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 12 ms 2592 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 2652 KB Output is correct
2 Correct 6 ms 2652 KB Output is correct
3 Correct 36 ms 2840 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 5192 KB Output is correct
2 Correct 7 ms 2652 KB Output is correct
3 Correct 212 ms 2984 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 457 ms 33556 KB Output is correct
2 Correct 11 ms 2652 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 980 ms 33612 KB Output is correct
2 Correct 56 ms 11536 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 807 ms 33348 KB Output is correct
2 Correct 110 ms 14292 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1020 ms 33232 KB Output is correct
2 Correct 243 ms 27192 KB Output is correct