#include<bits/stdc++.h>
#include "citymapping.h"
using namespace std;
const int N = 1000;
long long distances[N][N];
long long get_dst(int x, int y) {
if (x > y) {
swap(x, y);
}
auto &ret = distances[x][y];
if (~ret)
return ret;
}
return ret = get_distance(x + 1, y + 1);
}
long long &dist(int x, int y) {
if (x > y) {
swap(x, y);
}
return distances[x][y];
}
int sizeSubtree[N];
int counter;
vector<pair<int, int> > children[N];
bool visited[N];
vector<pair<int, int> > heavy;
void dfs(int u, int p) {
sizeSubtree[u] = 1;
counter++;
for (pair<int, int> x : adj[u]){
int v = x.first;
if (!visited[v]) {
dist(p, v) = dist(p, u) + to.second;
dfs(v, p);
sizeSubtree[u] += sizeSubtree[v];
}
}
}
int dfs2(int u) {
pair<int, int> maxVal = {-1, -1};
for (pair<int, int> x : children[u]){
int v = x.first;
if (!visited[v] && (maxVal.first == -1 || sizeSubtree[maxVal.first] < sizeSubtree[v])) {
maxVal = to;
}
}
if (~maxVal.first) {
heavy.push_back(maxVal);
return dfs2(maxVal.first);
}
return u;
}
void find_roads(int n, int q, int a[], int b[], int w[]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
distances[i][j] = -1;
}
}
for (int i = 0; i < n; i++) {
dist(i, i) = 0;
}
vector<pair<long long, int>> ds;
for (int i = 1; i < n; i++) {
ds.push_back({get_dst(0, i), i});
}
sort(ds.begin(), ds.end());
int m = 0;
for (auto &x: ds) {
int r = 0;
while (true) {
counter = 0;
dfs(r, r);
if (counter == 1) {
break;
}
int l = dfs2(r);
long long xl = get_dst(x.second, l), rm = (get_dst(r, x.second) + get_dst(r, l) - xl) / 2;
for (auto &y: heavy) {
visited[y.first] = 1;
}
int i = 0;
while (rm > 0) {
rm -= heavy[i++].second;
}
int M = (i ? heavy[i - 1].first: r);
dist(M, x.second) = (get_dst(r, x.second) + get_dst(l, x.second) - get_dst(r, l)) / 2;
heavy.clear();
r = M;
}
a[m] = 1 + r;
b[m] = 1 + x.second;
w[m] = dist(r, x.second);
children[r].push_back({b[m] - 1, w[m]});
dist(r, b[m] - 1) = w[m];
m++;
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
}
}
Compilation message
citymapping.cpp:14:2: error: expected unqualified-id before 'return'
14 | return ret = get_distance(x + 1, y + 1);
| ^~~~~~
citymapping.cpp:15:1: error: expected declaration before '}' token
15 | }
| ^
citymapping.cpp: In function 'void dfs(int, int)':
citymapping.cpp:30:26: error: 'adj' was not declared in this scope
30 | for (pair<int, int> x : adj[u]){
| ^~~
citymapping.cpp:33:30: error: 'to' was not declared in this scope; did you mean 'tm'?
33 | dist(p, v) = dist(p, u) + to.second;
| ^~
| tm
citymapping.cpp: In function 'int dfs2(int)':
citymapping.cpp:44:13: error: 'to' was not declared in this scope; did you mean 'tm'?
44 | maxVal = to;
| ^~
| tm
citymapping.cpp: In function 'long long int get_dst(int, int)':
citymapping.cpp:13:2: warning: control reaches end of non-void function [-Wreturn-type]
13 | }
| ^
