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;
void find_roads(int N, int Q, int A[], int B[], int W[]) {
vector<pair<long long, long long>> tree;
vector<long long> init(N+5);
int p = 0;
for(int i = 1; i < N; i ++){
tree.push_back({get_distance(1, i+1), i+1});
init[i+1] = tree.back().first;
}
sort(tree.begin(), tree.end());
vector<int> picks(N+20);
vector <long long> ends;
for(auto [j, i] : tree){
int picked = false;
sort(ends.begin(), ends.end(), [&](long long a, long long b){return init[a] > init[b];});
for(auto r : ends){
long long t = get_distance(r, i);
if(init[i] == init[r] + t){
picked = true;
A[p] = i;
B[p] = r;
W[p++] = t;
picks[r]++;
ends.push_back(i);
if(picks[r] == 2){
ends.erase(find(ends.begin(), ends.end(), r));
}
break;
}
}
if(!picked){
ends.push_back(i);
A[p] = 1;
B[p] = i;
W[p++] = init[i];
}
}
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... |