Submission #836511

#TimeUsernameProblemLanguageResultExecution timeMemory
836511unnickCity Mapping (NOI18_citymapping)C++14
57 / 100
39 ms18000 KiB
#include "citymapping.h" //#include <iostream> #include <functional> #include <algorithm> #include <numeric> #include <vector> using namespace std; #define ll long long typedef struct { int to; ll d; } edge_t; void find_roads(int N, int Q, int A[], int B[], int W[]) { if (Q <= 12000) { int start; { ll maxd = 0; for (int i = 2; i <= N; i++) { ll d = get_distance(1, i); if (d > maxd) { maxd = d; start = i; } } } vector<ll> dists(N); dists[start-1] = 0; vector<int> ids(N); iota(ids.begin(), ids.end(), 0); for (int i = 1; i <= N; i++) { if (i == start) continue; dists[i-1] = get_distance(start,i); } sort(ids.begin(), ids.end(), [&](int a, int b) { return dists[a] < dists[b]; }); for (int i = 0; i < N-1; i++) { A[i] = ids[i]+1; B[i] = ids[i+1]+1; W[i] = dists[ids[i+1]] - dists[ids[i]]; } } else { vector<ll> dists(N*N, -1); auto ds = [&](int i_, int j_){ i_--; j_--; int i = min(i_, j_); int j = max(i_, j_); if (dists[i+j*N] == -1) { dists[i+j*N] = get_distance(i+1, j+1); } return dists[i+j*N]; }; int out_idx = 0; auto output = [&](int x, int y, int dist) { A[out_idx] = x; B[out_idx] = y; W[out_idx++] = dist; }; // for (int i = 1; i <= N; i++) { // for (int j = i+1; j <= N; j++) { // // if (get_distance(i,j) == 1) { // // A[k] = i; // // B[k] = j; // // W[k++] = 1; // // } // dists[i+j*N] = dists[j+i*N] = get_distance(i,j); // } // } std::function<void(vector<edge_t>&, int, int)> rec = [&](vector<edge_t> &edges, int x, int a) -> void { if (edges.size() == 0) return; if (a == 2) { edge_t edge = edges[0]; output(x, edge.to, edge.d); for (int i = 1; i < edges.size(); i++) { edges[i-1] = edges[i]; edges[i-1].d -= edge.d; } edges.pop_back(); rec(edges, edge.to, 0); return; } vector<edge_t> sub; vector<edge_t> rest; int y = edges[0].to; output(x, y, edges[0].d); for (edge_t edge : edges) { if (edge.to == x || edge.to == y) continue; ll dist = ds(y, edge.to); if (dist < edge.d) { sub.push_back({.to = edge.to, .d = ds(y, edge.to)}); } else { rest.push_back(edge); } } sort(sub.begin(), sub.end(), [](edge_t a, edge_t b) { return a.d < b.d; }); rec(sub, y, 1); rec(rest, x, a+1); }; vector<edge_t> edges; for (int i = 2; i <= N; i++) { ll dist = ds(1, i); edges.push_back({.to = i, .d = dist}); } sort(edges.begin(), edges.end(), [](edge_t a, edge_t b) { return a.d < b.d; }); rec(edges, 1, 0); } }

Compilation message (stderr)

citymapping.cpp: In lambda function:
citymapping.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge_t>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 1; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:37:29: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |    dists[i-1] = get_distance(start,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...