#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
mt19937 rnd(time(NULL));
int n;
ll dis[N][N];
int A[N], B[N], W[N], tot;
ll d(int i, int j) {
if (i == j) return 0;
if (!dis[i][j]) return dis[i][j] = dis[j][i] = get_distance(i, j);
return dis[i][j];
}
void play(vector<int>& v, int U, int V) {
int m = v.size();
if (m == 1) return;
ll all = d(U, V);
vector<pair<ll, int>> in, rem;
for (auto& x : v) {
if (d(U, x) + d(x, V) == all) in.push_back({ d(V, x), x });
else {
ll extra = (d(U, x) + d(x, V) - all) / 2;
rem.push_back({ d(V, x) - extra, x });
}
}
sort(in.begin(), in.end());
sort(rem.begin(), rem.end());
vector<vector<int>> r;
vector<int> p2;
int p = 0;
for (int i = 1;i < (int)in.size();i++) {
A[tot] = in[i - 1].second;
B[tot] = in[i].second;
W[tot] = in[i].first - in[i - 1].first;
tot++;
vector<int> nw;
ll mn = LLONG_MAX;
int idx = 0;
while (p < (int)rem.size() && rem[p].first == in[i].first) {
int vl = rem[p].second;
ll extra = (d(U, vl) + d(vl, V) - all) / 2;
if (extra < mn) {
mn = extra;
idx = vl;
}
nw.push_back(vl);
p++;
}
if ((int)nw.size() >= 2) {
A[tot] = idx;
B[tot] = in[i].second;
W[tot] = mn;
tot++;
ll mx = -1;
int idx2 = 0;
for (auto& x : nw) {
dis[idx][x] = dis[x][idx] = d(V, x) - mn - in[i].first;
if (dis[idx][x] > mx) {
mx = dis[idx][x];
idx2 = x;
}
}
sort(nw.begin(), nw.end(), [&](int a, int b) {
return d(idx, a) < d(idx, b);
});
p2.push_back(idx);
r.push_back(nw);
}
}
for (int i = 0;i < (int)r.size();i++) {
play(r[i], r[i][r[i].size() - 2], r[i][r[i].size() - 1]);
}
}
void find_roads(int NN, int Q, int A[], int B[], int W[]) {
n = NN;
vector<int> init(n);
int rt = rnd() % n + 1;
iota(init.begin(), init.end(), 1);
int leaf = 0, leaf2 = 0;
ll mx = -1;
for (int i = 1;i <= n;i++) {
if (d(rt, i) > mx) {
mx = d(rt, i);
leaf = i;
}
}
sort(init.begin(), init.end(), [&](int a, int b) {
return d(rt, a) < d(rt, b);
});
play(init, init[n - 2], init[n - 1]);
for (int i = 0;i < n - 1;i++) {
A[i] = ::A[i];
B[i] = ::B[i];
W[i] = ::W[i];
//cout << A[i] << ' ' << B[i] << ' ' << W[i] << '\n';
}
return;
}
Compilation message
citymapping.cpp: In function 'void play(std::vector<int>&, int, int)':
citymapping.cpp:56:8: warning: variable 'idx2' set but not used [-Wunused-but-set-variable]
56 | int idx2 = 0;
| ^~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:80:6: warning: variable 'leaf' set but not used [-Wunused-but-set-variable]
80 | int leaf = 0, leaf2 = 0;
| ^~~~
citymapping.cpp:80:16: warning: unused variable 'leaf2' [-Wunused-variable]
80 | int leaf = 0, leaf2 = 0;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
14684 KB |
Reported list of edges differ from actual. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
14684 KB |
Reported list of edges differ from actual. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8540 KB |
Too many calls to get_distance(). |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8540 KB |
Too many calls to get_distance(). |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
14684 KB |
Reported list of edges differ from actual. |
| 2 |
Halted |
0 ms |
0 KB |
- |
