제출 #945490

#제출 시각아이디문제언어결과실행 시간메모리
945490vjudge1City Mapping (NOI18_citymapping)C++14
22 / 100
2066 ms4652 KiB
#include <bits/stdc++.h> #include "citymapping.h" using namespace std; void find_roads(int N, int Q, int A[], int B[], int W[]) { vector<vector<int>> dist(N, vector<int>(N)); auto ask = [&](int x, int y) { if (x == y) return 0; if (dist[x][y]) return dist[x][y]; return dist[x][y] = dist[y][x] = get_distance(x + 1, y + 1); }; vector<vector<int64_t>> adj(N); int counter = 0; auto add_edge = [&](int x, int y, int z) { A[counter] = x + 1; B[counter] = y + 1; W[counter++] = z; adj[x].emplace_back(y); }; vector<int> weight(N), done(N); function<int(int)> dfs = [&](int u) { weight[u] = 1; for (int v : adj[u]) { if (!done[v]) weight[u] += dfs(v); } return weight[u]; }; vector<int> cur(1, 0); vector<pair<int64_t, int>> dist_list; for (int i = 1; i < N; i++) { dist_list.emplace_back(ask(0, i), i); } sort(dist_list.begin(), dist_list.end()); vector<int64_t> depth(N); for (auto&& [d, j] : dist_list) { int root = 0; while (dfs(root) > 1) { vector<int> path(1, root); int leaf = root; while (adj[leaf].size()) { int _i, best = -1; for (int _j : adj[leaf]) { if (done[_j]) continue; if (best < weight[_j]) best = weight[_j], _i = _j; } if (best == -1) break; leaf = _i; path.emplace_back(leaf); } int64_t jr = ask(0, j) - ask(0, root); int64_t rl = ask(0, leaf) - ask(0, root); int64_t lj = ask(j, leaf); int64_t s = jr + rl + lj >> 1; int64_t r = s - lj; for (int i = 0; i < path.size(); i++) { int u = path[i]; if (ask(0, u) - ask(0, root) == r) { root = u; if (i + 1 < path.size()) done[path[i + 1]] = 1; // block the larger branch break; } } } add_edge(root, j, d - ask(0, root)); for (int i = 0; i < N; i++) done[i] = 0; } }

컴파일 시 표준 에러 (stderr) 메시지

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:42:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for (auto&& [d, j] : dist_list) {
      |                 ^
citymapping.cpp:60:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |             int64_t s = jr + rl + lj >> 1;
      |                         ~~~~~~~~^~~~
citymapping.cpp:62:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for (int i = 0; i < path.size(); i++) {
      |                             ~~^~~~~~~~~~~~~
citymapping.cpp:66:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |                     if (i + 1 < path.size()) done[path[i + 1]] = 1;  // block the larger branch
      |                         ~~~~~~^~~~~~~~~~~~~
#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...