# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1166936 | zh_h | City Mapping (NOI18_citymapping) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define pb push_back;
using namespace std;
void find_roads(int N, int Q, vector<int> A, vector<int> B, vector<int> W) {
// get N, Q
// pick a lucky number: 1
// find the difference of 1 and all other nodes
vector<pair<long long, int>> dis1; // {distance, node}
for (int i = 2; i <= N; i ++) {
dis1.pb({get_distance(1, i), i});
}
sort(dis1.begin(), dis1.end());
// get longest distance node
int longest_dis_node = dis1[N-2].second;
vector<pair<long long, int>> dis2;
for (int i = 1; i <= N; i ++) {
if (i == longest_dis_node) {continue;}
dis2.pb({get_distance(longest_dis_node, i), i});
}
sort(dis2.begin(), dis2.end());
int cur = 0;
for (int i = 0; i < dis2.size(); i ++) {
A.pb(longest_dis_node);
B.pb(dis2[i].second);
W.pb(dis2[i].first-cur);
cur = dis2[i].first;
}
}