제출 #377921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377921		rainboy	Jakarta Skyscrapers (APIO15_skyscraper)	C11	100 / 100	953 ms	175084 KiB

skyscraper

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

#define N	30000
#define M	30000
#define M_	11111111

int min(int a, int b) { return a < b ? a : b; }

void append(int **eh, int *eo, int i, int h) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

int main() {
	static int *eh1[N + 1], eo1[N + 1], *eh2[N + 1], eo2[N + 1];
	static int ii[M_], hh[N], nxt[M_ * 2], dd[M_], qu[M + M_];
	int n, m, m_, h, i, j, o, head, cnt;

	scanf("%d%d", &n, &m);
	for (i = 0; i <= n; i++) {
		eh1[i] = (int *) malloc(2 * sizeof *eh1[i]);
		eh2[i] = (int *) malloc(2 * sizeof *eh2[i]);
	}
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), j = min(j, n);
		ii[h] = i;
		append(eh1, eo1, i, h);
		append(eh2, eo2, j, h);
	}
	if (ii[0] == ii[1]) {
		printf("0\n");
		return 0;
	}
	m_ = m;
	memset(hh, -1, n * sizeof *hh);
	memset(nxt, -1, sizeof nxt);
	for (j = 1; j < n; j++) {
		for (o = eo2[j]; o--; ) {
			h = eh2[j][o];
			hh[ii[h]] = h;
		}
		for (o = eo2[j]; o--; ) {
			int h_, h1;

			h = eh2[j][o];
			if (hh[ii[h]] == -1)
				continue;
			h_ = -1;
			for (i = ii[h] % j; i < n; i += j) {
				if (hh[i] == -1)
					ii[h1 = m_++] = i;
				else
					h1 = hh[i], hh[i] = -1;
				if (h_ != -1)
					nxt[h_ << 1 | 1] = h1, nxt[h1 << 1 | 0] = h_;
				h_ = h1;
			}
		}
	}
	for (h = 0; h < m_; h++)
		dd[h] = m_;
	head = m, cnt = 0;
	dd[0] = 0, qu[head + cnt++] = 0;
	while (cnt) {
		int d, o, h_;

		h = qu[cnt--, head++], i = ii[h], d = dd[h];
		if (h == 1) {
			printf("%d\n", d);
			return 0;
		}
		if (eo1[i]) {
			for (o = eo1[i]; o--; ) {
				h_ = eh1[i][o];
				if (dd[h_] > d)
					dd[h_] = d, qu[cnt++, --head] = h_;
			}
			eo1[i] = 0;
		}
		d++;
		h_ = nxt[h << 1 | 0];
		if (h_ != -1 && dd[h_] > d)
			dd[h_] = d, qu[head + cnt++] = h_;
		h_ = nxt[h << 1 | 1];
		if (h_ != -1 && dd[h_] > d)
			dd[h_] = d, qu[head + cnt++] = h_;
	}
	printf("-1\n");
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.c: In function 'append':
skyscraper.c:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
skyscraper.c: In function 'main':
skyscraper.c:24:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   24 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
skyscraper.c:30:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   30 |   scanf("%d%d", &i, &j), j = min(j, n);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43