#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <string.h>
#define N 30000
#define INF 0x3f3f3f3f
unsigned int X;
void srand() {
struct timeval tv;
gettimeofday(&tv, NULL);
X = tv.tv_sec ^ tv.tv_usec | 1;
}
int rand() {
return (X *= 3) >> 1;
}
int *ed[N], eo[N], *ej[N], *ew[N], eo_[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ed[i] = (int *) realloc(ed[i], o * 2 * sizeof *ed[i]);
ed[i][o] = j;
}
void append_(int i, int j, int 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] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
}
ej[i][o] = j, ew[i][o] = w;
}
void sort(int *aa, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, a_ = aa[l + rand() % (r - l)], tmp;
while (j < k) {
int c = aa[j] - a_;
if (c == 0)
j++;
else if (c < 0) {
tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
i++, j++;
} else {
k--;
tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
}
}
sort(aa, l, i);
l = k;
}
}
int find(int i, int d) {
int lower = 0, upper = eo[i] - 1;
while (lower < upper) {
int t = (lower + upper) / 2;
if (ed[i][t] < d)
lower = t + 1;
else if (ed[i][t] > d)
upper = t - 1;
else
return 1;
}
return 0;
}
int dd[N], pq[1 + N], iq[N], cnt;
#define LT(u, v) (dd[u] < dd[v])
int i2(int i) {
return (i *= 2) > cnt ? 0 : i < cnt && LT(pq[i + 1], pq[i]) ? i + 1 : i;
}
void pq_up(int u) {
int i, j;
for (i = iq[u]; (j = i / 2) && LT(u, pq[j]); i = j)
pq[iq[pq[j]] = i] = pq[j];
pq[iq[u] = i] = u;
}
void pq_dn(int u) {
int i, j;
for (i = iq[u]; (j = i2(i)) && LT(pq[j], u); i = j)
pq[iq[pq[j]] = i] = pq[j];
pq[iq[u] = i] = u;
}
void pq_add(int u) {
iq[u] = ++cnt;
pq_up(u);
}
int pq_remove_first() {
int u = pq[1], v = pq[cnt--];
iq[v] = 1;
pq_dn(v);
return u;
}
int main() {
int n, m, i, j, d, s, t;
srand();
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++) {
ed[i] = (int *) malloc(2 * sizeof *ed[i]), eo[i] = 0;
ej[i] = (int *) malloc(2 * sizeof *ej[i]), ew[i] = (int *) malloc(2 * sizeof *ew[i]), eo_[i] = 0;
}
s = t = -1;
for (i = 0; i < m; i++) {
scanf("%d%d", &j, &d);
if (i == 0)
s = j;
else if (i == 1)
t = j;
append(j, d);
}
for (i = 0; i < n; i++)
sort(ed[i], 0, eo[i]);
for (i = 0; i < n; i++) {
int o;
for (o = eo[i]; o--; ) {
d = ed[i][o];
for (j = i; j < n; j += d) {
append_(i, j, (j - i) / d);
if (find(j, d))
break;
}
for (j = i; j >= 0; j -= d) {
append_(i, j, (i - j) / d);
if (find(j, d))
break;
}
}
}
memset(dd, 0x3f, n * sizeof *dd);
dd[s] = 0;
pq_add(s);
while (cnt) {
int o;
i = pq_remove_first();
for (o = eo_[i]; o--; ) {
int j = ej[i][o], w = ew[i][o];
d = dd[i] + w;
if (dd[j] == INF) {
dd[j] = d;
pq_add(j);
} else if (d < dd[j]) {
dd[j] = d;
pq_up(j);
}
}
}
printf("%d\n", dd[t] == INF ? -1 : dd[t]);
}
Compilation message
skyscraper.c: In function 'srand':
skyscraper.c:11:1: error: number of arguments doesn't match prototype
11 | void srand() {
| ^~~~
In file included from skyscraper.c:2:
/usr/include/stdlib.h:455:13: error: prototype declaration
455 | extern void srand (unsigned int __seed) __THROW;
| ^~~~~
skyscraper.c:15:16: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
15 | X = tv.tv_sec ^ tv.tv_usec | 1;
| ~~~~~~~~~~^~~~~~~~~~~~
skyscraper.c: In function 'append':
skyscraper.c:27:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
27 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
skyscraper.c: In function 'append_':
skyscraper.c:35:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
35 | if (o >= 2 && (o & o - 1) == 0) {
| ~~^~~
skyscraper.c: In function 'main':
skyscraper.c:120:2: error: too few arguments to function 'srand'
120 | srand();
| ^~~~~
In file included from skyscraper.c:2:
/usr/include/stdlib.h:455:13: note: declared here
455 | extern void srand (unsigned int __seed) __THROW;
| ^~~~~
skyscraper.c:121:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
skyscraper.c:128:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
128 | scanf("%d%d", &j, &d);
| ^~~~~~~~~~~~~~~~~~~~~
