제출 #762821

#제출 시각아이디문제언어결과실행 시간메모리
762821rainboyTravelling Merchant (CCO21_day2problem1)C11
0 / 25
237 ms38604 KiB
#include <stdio.h> #include <stdlib.h> #define N 200000 #define M 200000 #define INF 0x3f3f3f3f int max(int a, int b) { return a > b ? a : b; } int *eh[N], eo[N], *fh[N], fo[N], dd[N], dd_[N], n; int ii[M], jj[M], xx[M], yy[M], m; 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 pq[N + M], *iq[N + 1], cnt[N + 1], mode; int lt_h(int h1, int h2) { int j1 = jj[h1], w1 = max(xx[h1], (dd[j1] == INF ? INF : dd[j1] - yy[h1])); int j2 = jj[h2], w2 = max(xx[h2], (dd[j2] == INF ? INF : dd[j2] - yy[h2])); return w1 < w2; } int lt_i(int i, int j) { return dd_[i] > dd_[j]; } int (*compare)(int, int); int lt(int i, int j) { return mode < n ? lt_h(i - n, j - n) : lt_i(i, j); } int p2(int p) { return (p *= 2) > cnt[mode] ? 0 : (p < cnt[mode] && lt(iq[mode][p + 1], iq[mode][p]) ? p + 1 : p); } void pq_up(int i) { int p, q, j; for (p = pq[i]; (q = p / 2) && lt(i, j = iq[mode][q]); p = q) iq[mode][pq[j] = p] = j; iq[mode][pq[i] = p] = i; } void pq_dn(int i) { int p, q, j; for (p = pq[i]; (q = p2(p)) && lt(j = iq[mode][q], i); p = q) iq[mode][pq[j] = p] = j; iq[mode][pq[i] = p] = i; } void pq_add(int i) { pq[i] = ++cnt[mode], pq_up(i); } int pq_first() { return iq[mode][1]; } int pq_remove_first() { int i = iq[mode][1], j = iq[mode][cnt[mode]--]; if (j != i) pq[j] = 1, pq_dn(j); pq[i] = 0; return i; } int main() { int h, i, j, j_, x, y, o; scanf("%d%d", &n, &m); for (i = 0; i < n; i++) { eh[i] = (int *) malloc(2 * sizeof *eh[i]); fh[i] = (int *) malloc(2 * sizeof *fh[i]); } for (h = 0; h < m; h++) { scanf("%d%d%d%d", &i, &j, &x, &y), i--, j--; ii[h] = i, jj[h] = j, xx[h] = x, yy[h] = y; append(eh, eo, i, h), append(fh, fo, j, h); } for (i = 0; i < n; i++) { mode = i; iq[mode] = (int *) malloc((eo[i] + 1) * sizeof *iq[mode]); for (o = eo[i]; o--; ) { h = eh[i][o]; pq_add(n + h); } if (cnt[i] == 0) dd_[i] = INF; else { h = pq_first() - n, j = jj[h]; dd_[i] = max(xx[h], (dd[j] == INF ? INF : dd[j] - yy[h])); } } mode = n; iq[mode] = (int *) malloc((n + 1) * sizeof *iq[mode]); for (i = 0; i < n; i++) pq_add(i); while (cnt[mode = n]) { j = pq_remove_first(); dd[j] = dd_[j]; for (o = fo[j]; o--; ) { h = fh[j][o], i = ii[h]; mode = i, pq_dn(n + h); if (cnt[i] == 0) dd_[i] = INF; else { h = pq_first() - n, j_ = jj[h]; dd_[i] = max(xx[h], (dd[j_] == INF ? INF : dd[j_] - yy[h])); } mode = n, pq_up(i); } } for (i = 0; i < n; i++) printf("%d ", dd[i] == INF ? -1 : dd[i]); printf("\n"); return 0; }

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

Main.c: In function 'append':
Main.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:78:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:84:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d%d%d%d", &i, &j, &x, &y), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...