#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1e15;
void find_roads(int N, int Q, int A[], int B[], int W[]) {
int r = -1;
ll mx = 0;
for (int i = 1; i < N; i++) {
ll s = get_distance(1, i + 1);
Q--;
if (s > mx) {
mx = s;
r = i;
}
}
vector<ll> dis(N);
for (int i = 0; i < N; i++) {
dis[i] = i == r ? 0 : get_distance(r + 1, i + 1);
}
vector<int> p(N);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j) {
return dis[i] < dis[j];
});
vector<vector<int>> ch(N);
for (int i = 1; i < N; i++) {
int x = r, v = p[i];
while (1) {
if (ch[x].empty()) {
A[i - 1] = x + 1;
B[i - 1] = v + 1;
W[i - 1] = dis[v] - dis[x];
ch[x].push_back(v);
break;
}
if (x == r) {
x = ch[x][0];
continue;
}
if (ch[x].size() == 2) {
if (get_distance(v + 1, ch[x][0] + 1) < get_distance(v + 1, ch[x][1] + 1)) {
x = ch[x][0];
} else {
x = ch[x][1];
}
} else {
assert(ch[x].size() == 1);
if (get_distance(v + 1, x + 1) < get_distance(v + 1, ch[x][0] + 1)) {
A[i - 1] = x + 1;
B[i - 1] = v + 1;
W[i - 1] = dis[v] - dis[x];
ch[x].push_back(v);
break;
}
x = ch[x][0];
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
468 KB |
Too many calls to get_distance(). |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 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 |
464 KB |
Too many calls to get_distance(). |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
464 KB |
Too many calls to get_distance(). |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
468 KB |
Too many calls to get_distance(). |
| 2 |
Halted |
0 ms |
0 KB |
- |
