#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;
const int nax = 1002;
#define int long long
struct Dsu {
int par[nax];
int sz[nax];
Dsu() {
for(int i = 0; i < nax; i++) {
par[i] = i;
sz[i] = 1;
}
}
int find(int v) {
if (v == par[v]) {
return v;
}
return par[v] = find(par[v]);
}
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (sz[b] > sz[a]) swap(a, b);
par[b] = a;
sz[a] += sz[b];
return true;
}
};
int dist[nax][nax];
int get_dist(int a, int b) {
if (dist[a][b] != 0) {
return dist[a][b];
}
return dist[a][b] = get_distance(a, b);
}
void brute(int N, int* A, int* B, int* W) {
vector<array<int, 3>> d;
for(int i = 1; i <= N; i++) {
for(int j = i+1; j <= N; j++) {
get_dist(i, j);
d.push_back({dist[i][j], i, j});
}
}
sort(d.begin(), d.end());
Dsu dsu;
int idx = 0;
for(auto& i : d) {
if (dsu.unite(i[1], i[2])) {
A[idx] = i[1];
B[idx] = i[2];
W[idx] = i[0];
idx++;
}
}
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
if (Q == 500000) {
brute(N, A, B, W);
return;
}
vector<array<int, 2>> d;
for(int i = 2; i <= N; i++) {
d.push_back({get_dist(1, i), i});
}
sort(d.begin(), d.end());
//for(auto& i : d) {
//cout << i[0] << " " << i[1] << "\n";
//}
A[0] = 1, B[0] = d[0][1], W[0] = d[0][0];
if (N == 2) return;
vector<int> child{B[0]};
for(int i = 1; i < N-1; i++) {
bool found = false;
for(int& u : child) {
if (d[i][0] == get_dist(1, u) + get_dist(u, d[i][1])) {
found = true;
A[i] = u;
B[i] = d[i][1];
u = B[i];
break;
}
}
if (!found) {
A[i] = 1;
B[i] = d[i][1];
child.push_back(B[i]);
assert(get_dist(1, d[i][1]) == d[i][0]);
}
W[i] = get_dist(A[i], B[i]);
}
//for(int i = 0; i < N; i++) {
//cout << A[i] << " " << B[i] << " " << W[i] << "\n";
//}
//for(auto& i : d) {
//cout << i[0] << " " << i[1] << "\n";
//}
return;
}
Compilation message
/usr/bin/ld: /tmp/ccLLnq3Q.o: in function `main':
grader.cpp:(.text.startup+0x39a): undefined reference to `find_roads(int, int, int*, int*, int*)'
collect2: error: ld returned 1 exit status
