제출 #1024459

#제출 시각아이디문제언어결과실행 시간메모리
1024459thinknoexitCity Mapping (NOI18_citymapping)C++17
57 / 100
93 ms18276 KiB
#include "citymapping.h" #include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1010; int n; ll dis[N][N]; int p[N]; int fr(int i) { return p[i] == i ? i : p[i] = fr(p[i]); } ll d(int i, int j) { if (i == j) return 0; if (!dis[i][j]) return dis[i][j] = dis[j][i] = get_distance(i, j); return dis[i][j]; } void find_roads(int NN, int Q, int A[], int B[], int W[]) { n = NN; if (Q == 12000) { ll mx = 0; int idx = 0; for (int i = 2;i <= n;i++) { if (d(1, i) > mx) { mx = d(1, i); idx = i; } } vector<pair<ll, int>> v; for (int i = 1;i <= n;i++) { v.push_back({ d(idx, i), i }); } sort(v.begin(), v.end()); for (int i = 1;i < n;i++) { A[i - 1] = v[i - 1].second; B[i - 1] = v[i].second; W[i - 1] = v[i].first - v[i - 1].first; } return; } vector<pair<ll, pair<int, int>>> v; for (int i = 1;i <= n;i++) { p[i] = i; for (int j = i + 1;j <= n;j++) { v.push_back({ d(i, j), {i, j} }); } } int idx = 0; sort(v.begin(), v.end()); for (auto& x : v) { int u = x.second.first, v = x.second.second; if (fr(u) == fr(v)) continue; p[fr(u)] = fr(v); A[idx] = u, B[idx] = v, W[idx] = x.first; idx++; } 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...