Submission #1024908

#TimeUsernameProblemLanguageResultExecution timeMemory
1024908thinknoexitCity Mapping (NOI18_citymapping)C++17
0 / 100
47 ms14672 KiB
#include "citymapping.h" #include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1010; mt19937 rnd(time(NULL)); 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 U, int V) { int m = v.size(); if (m == 1) return; ll all = d(U, V); vector<pair<ll, int>> in, rem; for (auto& x : v) { if (d(U, x) + d(x, V) == all) in.push_back({ d(V, x), x }); else { ll extra = (d(U, x) + d(x, V) - all) / 2; rem.push_back({ d(V, x) - extra, x }); } } sort(in.begin(), in.end()); sort(rem.begin(), rem.end()); vector<vector<int>> r; vector<int> p2; 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++; if ((int)nw.size() == 1) continue; ll mx = -1; int idx2 = 0; for (auto& x : nw) { dis[idx][x] = dis[x][idx] = d(V, x) - mn - in[i].first; if (dis[idx][x] > mx) { mx = dis[idx][x]; idx2 = x; } } sort(nw.begin(), nw.end(), [&](int a, int b) { return d(idx, a) < d(idx, b); }); p2.push_back(idx); r.push_back(nw); } } for (int i = 0;i < (int)r.size();i++) { play(r[i], r[i][r[i].size() - 2], r[i][r[i].size() - 1]); } } void find_roads(int NN, int Q, int A[], int B[], int W[]) { n = NN; vector<int> init(n); int rt = rnd() % n + 1; iota(init.begin(), init.end(), 1); int leaf = 0, leaf2 = 0; ll mx = -1; for (int i = 1;i <= n;i++) { if (d(rt, i) > mx) { mx = d(rt, i); leaf = i; } } sort(init.begin(), init.end(), [&](int a, int b) { return d(rt, a) < d(rt, b); }); play(init, init[n - 2], init[n - 1]); 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>&, int, int)':
citymapping.cpp:57:8: warning: variable 'idx2' set but not used [-Wunused-but-set-variable]
   57 |    int idx2 = 0;
      |        ^~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:81:6: warning: variable 'leaf' set but not used [-Wunused-but-set-variable]
   81 |  int leaf = 0, leaf2 = 0;
      |      ^~~~
citymapping.cpp:81:16: warning: unused variable 'leaf2' [-Wunused-variable]
   81 |  int leaf = 0, leaf2 = 0;
      |                ^~~~~
#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...