Submission #1024578

#TimeUsernameProblemLanguageResultExecution timeMemory
1024578thinknoexitCity Mapping (NOI18_citymapping)C++17
57 / 100
4 ms8796 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 A[N], B[N], W[N], tot; 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 play(vector<int>& v) { int m = v.size(); if (m == 1) return; ll mx = 0; int U, V; for (int j = 1;j < m;j++) { if (d(v[0], v[j]) > mx) { mx = d(v[0], v[j]); U = v[j]; } } mx = 0; for (int j = 0;j < m;j++) { if (d(U, v[j]) > mx) { mx = d(U, v[j]); V = v[j]; } } // U, V is leaf ll all = d(U, V); vector<pair<ll, int>> in, rem; for (int j = 0;j < m;j++) { if (d(U, v[j]) + d(v[j], V) == all) { in.push_back({ d(U, v[j]), v[j] }); } else { ll extra = (d(U, v[j]) + d(v[j], V) - all) / 2; rem.push_back({ d(U, v[j]) - extra, v[j] }); } } sort(in.begin(), in.end()); sort(rem.begin(), rem.end()); vector<vector<int>> r; int p = 0; for (int i = 1;i < (int)in.size();i++) { A[tot] = in[i - 1].second; B[tot] = in[i].second; W[tot] = in[i].first - in[i - 1].first; tot++; vector<int> nw; ll mn = LLONG_MAX; int idx = 0; while (p < (int)rem.size() && rem[p].first == in[i].first) { int vl = rem[p].second; ll extra = (d(U, vl) + d(vl, V) - all) / 2; if (extra < mn) { mn = extra; idx = vl; } nw.push_back(vl); p++; } if (!nw.empty()) { A[tot] = idx; B[tot] = in[i].second; W[tot] = mn; tot++; r.push_back(nw); } } for (auto& x : r) play(x); } void find_roads(int NN, int Q, int A[], int B[], int W[]) { n = NN; vector<int> init(n); iota(init.begin(), init.end(), 1); play(init); for (int i = 0;i < n - 1;i++) { A[i] = ::A[i]; B[i] = ::B[i]; W[i] = ::W[i]; //cout << A[i] << ' ' << B[i] << ' ' << W[i] << '\n'; } return; }

Compilation message (stderr)

citymapping.cpp: In function 'void play(std::vector<int>&)':
citymapping.cpp:10:2: warning: 'U' may be used uninitialized in this function [-Wmaybe-uninitialized]
   10 |  if (i == j) return 0;
      |  ^~
citymapping.cpp:18:6: note: 'U' was declared here
   18 |  int U, V;
      |      ^
citymapping.cpp:10:2: warning: 'V' may be used uninitialized in this function [-Wmaybe-uninitialized]
   10 |  if (i == j) return 0;
      |  ^~
citymapping.cpp:18:9: note: 'V' was declared here
   18 |  int U, V;
      |         ^
#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...