Submission #836380

#TimeUsernameProblemLanguageResultExecution timeMemory
836380LiudasCity Mapping (NOI18_citymapping)C++17
41 / 100
38 ms492 KiB
#include "citymapping.h" #include <bits/stdc++.h> using namespace std; void find_roads(int N, int Q, int A[], int B[], int W[]) { if(Q == 500000){ int p = 0; for(int i = 0; i < N; i ++){ for(int j = i + 1; j < N; j ++){ int t = get_distance(i+1, j+1); if(t == 1){ A[p] = i+1; B[p] = j+1; W[p++] = 1; } } } } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...