# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
733970 | vjudge1 | City Mapping (NOI18_citymapping) | C++17 | 117 ms | 8780 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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[]) {
if (Q == 500000) {
vector<tuple<ll, int, int>> T;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
T.emplace_back(get_distance(i + 1, j + 1), i, j);
}
}
sort(T.begin(), T.end());
vector<int> par(N);
iota(par.begin(), par.end(), 0);
function<int(int)> find = [&](int x) {
return x == par[x] ? x : par[x] = find(par[x]);
};
int p = 0;
for (int i = 0; i < T.size(); i++) {
auto [z, x, y] = T[i];
if (find(x) != find(y)) {
A[p] = x + 1;
B[p] = y + 1;
W[p] = z;
p++;
par[find(x)] = find(y);
}
}
return;
}
if (Q == 12000) {
int x = -1;
ll mx = 0;
for (int i = 1; i < N; i++) {
ll s = get_distance(1, i + 1);
if (s > mx) {
mx = s;
x = i;
}
}
vector<pair<ll, int>> p(N);
for (int i = 0; i < N; i++) {
p[i] = {get_distance(x + 1, i + 1), i};
}
sort(p.begin(), p.end());
for (int i = 0; i < N - 1; i++) {
A[i] = p[i].second + 1;
B[i] = p[i + 1].second + 1;
W[i] = p[i + 1].first - p[i].first;
}
return;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |