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;
vector<int> par;
int get(int x){
if(par[x] != x){
return par[x] = get(par[x]);
}
return x;
}
void merge(int a, int b){
par[get(a)] = get(b);
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
if(Q == 500000){
par.resize(N + 5);
iota(par.begin(), par.end(), 0);
vector<vector<long long>> tree;
int p = 0;
for(int i = 0; i < N; i ++){
for(int j = i + 1; j < N; j ++){
tree.push_back({get_distance(i+1, j+1), i+1, j+1});
}
}
sort(tree.begin(), tree.end());
for(auto i : tree){
int a = i[0], b = i[1], c = i[2];
if(get(b) != get(c)){
merge(b,c);
A[p] = b;
B[p] = c;
W[p++] = a;
}
}
}
else{
vector<pair<long long, long long>> dist(N, {0, 0});
for(int i = 1; i < N; i ++){
dist[i] = {get_distance(1, i + 1), i};
}
sort(dist.rbegin(), dist.rend());
for(int i = 1; i < N; i ++){
dist[i] = {get_distance(dist[i].second + 1, dist[0].second + 1), dist[i].second};
}
long long total = 0;
dist[0] = {0, dist[0].second};
sort(dist.begin(), dist.end());
for(int i = 1; i < N; i ++){
W[i-1] = dist[i].first - total;
A[i-1] = dist[i-1].second + 1;
B[i-1] = dist[i].second + 1;
total += W[i-1];
}
}
return;
}
# | 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... |