#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;
}
}
Compilation message
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 time |
Memory |
Grader output |
1 |
Correct |
15 ms |
4444 KB |
Correct: 2691 out of 500000 queries used. |
2 |
Correct |
9 ms |
4444 KB |
Correct: 2421 out of 500000 queries used. |
3 |
Correct |
9 ms |
4444 KB |
Correct: 4517 out of 500000 queries used. |
4 |
Correct |
9 ms |
4440 KB |
Correct: 5567 out of 500000 queries used. |
5 |
Correct |
11 ms |
4444 KB |
Correct: 3387 out of 500000 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
4444 KB |
Correct: 2691 out of 500000 queries used. |
2 |
Correct |
9 ms |
4444 KB |
Correct: 2421 out of 500000 queries used. |
3 |
Correct |
9 ms |
4444 KB |
Correct: 4517 out of 500000 queries used. |
4 |
Correct |
9 ms |
4440 KB |
Correct: 5567 out of 500000 queries used. |
5 |
Correct |
11 ms |
4444 KB |
Correct: 3387 out of 500000 queries used. |
6 |
Execution timed out |
2017 ms |
4580 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
4444 KB |
Correct: 2086 out of 12000 queries used. |
2 |
Correct |
12 ms |
4604 KB |
Correct: 2304 out of 12000 queries used. |
3 |
Correct |
16 ms |
4652 KB |
Correct: 2457 out of 12000 queries used. |
4 |
Correct |
12 ms |
4444 KB |
Correct: 2470 out of 12000 queries used. |
5 |
Correct |
12 ms |
4608 KB |
Correct: 2240 out of 12000 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
4444 KB |
Correct: 2086 out of 12000 queries used. |
2 |
Correct |
12 ms |
4604 KB |
Correct: 2304 out of 12000 queries used. |
3 |
Correct |
16 ms |
4652 KB |
Correct: 2457 out of 12000 queries used. |
4 |
Correct |
12 ms |
4444 KB |
Correct: 2470 out of 12000 queries used. |
5 |
Correct |
12 ms |
4608 KB |
Correct: 2240 out of 12000 queries used. |
6 |
Execution timed out |
2066 ms |
4444 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
4444 KB |
Correct: 2691 out of 500000 queries used. |
2 |
Correct |
9 ms |
4444 KB |
Correct: 2421 out of 500000 queries used. |
3 |
Correct |
9 ms |
4444 KB |
Correct: 4517 out of 500000 queries used. |
4 |
Correct |
9 ms |
4440 KB |
Correct: 5567 out of 500000 queries used. |
5 |
Correct |
11 ms |
4444 KB |
Correct: 3387 out of 500000 queries used. |
6 |
Execution timed out |
2017 ms |
4580 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |