Submission #733966

#TimeUsernameProblemLanguageResultExecution timeMemory
733966vjudge1City Mapping (NOI18_citymapping)C++17
57 / 100
120 ms8880 KiB
#include "citymapping.h" #include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll inf = 1e15; void find_roads(int N, int Q, int A[], int B[], int W[]) { if (Q == 500000) { vector<tuple<ll, int, int>> T; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { T.emplace_back(get_distance(i + 1, j + 1), i, j); } } sort(T.begin(), T.end()); vector<int> par(N); iota(par.begin(), par.end(), 0); function<int(int)> find = [&](int x) { return x == par[x] ? x : par[x] = find(par[x]); }; int p = 0; for (int i = 0; i < T.size(); i++) { auto [z, x, y] = T[i]; if (find(x) != find(y)) { A[p] = x + 1; B[p] = y + 1; W[p] = z; p++; par[find(x)] = find(y); } } return; } if (Q == 12000) { int x = -1; ll mx = 0; for (int i = 1; i < N; i++) { ll s = get_distance(1, i + 1); if (s > mx) { mx = s; x = i; } } vector<pair<ll, int>> p(N); for (int i = 0; i < N; i++) { p[i] = {get_distance(x + 1, i + 1), i}; } sort(p.begin(), p.end()); for (int i = 0; i < N - 1; i++) { A[i] = p[i].second + 1; B[i] = p[i + 1].second + 1; W[i] = p[i + 1].first - p[i].first; } return; } int r = -1; ll mx = 0; for (int i = 1; i < N; i++) { ll s = get_distance(1, i + 1); if (s > mx) { mx = s; r = i; } } vector<ll> dis(N); for (int i = 0; i < N; i++) { dis[i] = i == r ? 0 : get_distance(r + 1, i + 1); } vector<int> p(N); iota(p.begin(), p.end(), 0); sort(p.begin(), p.end(), [&](int i, int j) { return dis[i] < dis[j]; }); vector<vector<int>> d(N); d[0].push_back(r); for (int i = 1; i < N; i++) { int v = p[i]; vector<bool> f(N); int lo = 0, hi = N - 1; while (lo < hi) { int mi = (lo + hi + 1) / 2; bool ok = 0; for (int x : d[mi]) { if (dis[v] - dis[x] > 0 && dis[v] - dis[x] == get_distance(x + 1, v + 1)) { f[x] = 1; ok = 1; break; } } if (ok) { lo = mi; } else { hi = mi - 1; } } int u = -1; for (int x : d[lo]) { if (f[x]) { u = x; } } if (u == -1) { for (int x : d[lo]) { if (dis[v] - dis[x] > 0 && dis[v] - dis[x] == get_distance(x + 1, v + 1)) { u = x; break; } } } A[i - 1] = u + 1; B[i - 1] = v + 1; W[i - 1] = dis[v] - dis[u]; d[lo + 1].push_back(v); } }

Compilation message (stderr)

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for (int i = 0; i < T.size(); 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...