#include "citymapping.h"
#include <stdio.h>
#include <stdlib.h>
const int N = 1000;
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int *ej[N], eo[N], jj[N], jj_[N]; long long dd[N];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (dd[ii[j]] == dd[i_])
j++;
else if (dd[ii[j]] < dd[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
void append(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 dfs(int i) {
int s = 1, k_ = 0, j_ = -1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o], k = dfs(j);
s += k;
if (k_ < k)
k_ = k, j_ = j;
}
jj[i] = j_;
jj_[i] = j_ == -1 ? i : jj_[jj[i]];
return s;
}
void find_roads(int n, int q, int uu[], int vv[], int ww[]) {
static int ii[N];
for (int i = 1; i < n; i++)
dd[i] = get_distance(1, i + 1);
for (int i = 1; i < n; i++)
ii[i] = i;
sort(ii, 1, n);
for (int i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
for (int h = 1; h < n; h++) {
int k = ii[h];
dfs(0);
int i = 0;
while (1) {
if (eo[i] == 0) {
append(i, k);
uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
break;
}
long long d_ = (dd[jj_[i]] + dd[k] - get_distance(jj_[i] + 1, k + 1)) / 2;
if (i != 0 || dd[i] < d_) {
while (dd[i] < d_)
i = jj[i];
if (eo[i] <= 1) {
append(i, k);
uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
break;
}
i = ej[i][0] ^ ej[i][1] ^ jj_[i];
} else {
if (eo[i] == 1) {
append(i, k);
uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
break;
} else {
int j = ej[i][0];
if (j == jj_[i])
j = ej[i][1];
long long d_ = (dd[jj_[j]] + dd[k] - get_distance(jj_[j] + 1, k + 1)) / 2;
if (dd[i] < d_) {
i = j;
while (dd[i] < d_)
i = jj[i];
if (eo[i] <= 1) {
append(i, k);
uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
break;
}
i = ej[i][0] ^ ej[i][1] ^ jj_[i];
} else {
if (eo[i] == 2) {
append(i, k);
uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
break;
} else
i = ej[i][0] ^ ej[i][1] ^ ej[i][2] ^ jj_[i] ^ j;
}
}
}
}
}
for (int i = 0; i < n; i++)
free(ej[i]);
}
Compilation message
citymapping.cpp: In function 'void append(int, int)':
citymapping.cpp:35:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
35 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Too many calls to get_distance(). |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Too many calls to get_distance(). |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
