Submission #961462

#TimeUsernameProblemLanguageResultExecution timeMemory
961462vjudge1City Mapping (NOI18_citymapping)C++17
25 / 100
42 ms13652 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ent "\n" const int maxn = 1e3 + 100; const ll INF = (ll)1e18 + 100; const int inf = 1e9 + 100; const int MOD = 1e9 + 7; const int maxl = 30; const int P = 31; long long get_distance(int X, int Y); int n; ll d[maxn][maxn]; vector<pii> ans; void calc(vector<int> v){ sort(v.begin(), v.end(), [](int i, int j){ return d[1][i] < d[1][j]; }); vector<vector<int>> to; for(int i: v){ if(i == v[0]) continue; bool ok = 1; for(auto &s: to){ if(d[v[0]][s[0]] + d[s[0]][i] == d[v[0]][i]){ s.push_back(i); ok = 0; break; } } if(ok) to.push_back({i}); } for(auto &s: to){ ans.push_back({v[0], s[0]}); calc(s); } } void find_roads(int N, int Q, int A[], int B[], int W[]){ n = N; for(int i = 1; i <= n; i++){ for(int j = i + 1; j <= n; j++){ d[i][j] = d[j][i] = get_distance(i, j); } } vector<int> v; for(int i = 1; i <= n; i++){ v.push_back(i); } calc(v); for(int i = 0; i < n-1; i++){ A[i] = ans[i].first; B[i] = ans[i].second; W[i] = d[A[i]][B[i]]; } }
#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...