#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
vector<int> childs;
vector<int> dists;
};
void dfs(int head, int par, int dist, vector<node> &tree, vector<int> &good, int d){
if((head == 1 || tree[head].childs.size() < 2) && d < dist){
good.push_back(head);
}
for(int i = 0; i < tree[head].childs.size(); i ++){
dfs(tree[head].childs[i], -1, dist, tree, good, d + tree[head].dists[i]);
}
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
vector<pair<long long, long long>> tree;
vector<long long> init(N+5);
int p = 0;
for(int i = 1; i < N; i ++){
tree.push_back({get_distance(1, i+1), i+1});
init[i+1] = tree.back().first;
}
sort(tree.begin(), tree.end());
vector<int> picks(N+20);
picks[0] = -1e9;
vector <long long> ends;
ends.push_back(1);
vector<node> arr(N + 20);
for(auto [j, i] : tree){
sort(ends.begin(), ends.end(), [&](long long a, long long b){return init[a] < init[b];});
int t = get_distance(ends.back(), i);
vector<int> good;
dfs(ends.back(), -1, t, arr, good, 0);
sort(good.begin(), good.end(), [&](long long a, long long b){return init[a] > init[b];});
for(auto r : good){
long long t = get_distance(r, i);
if(init[i] == init[r] + t){
A[p] = i;
B[p] = r;
W[p++] = t;
picks[r]++;
ends.push_back(i);
arr[r].childs.push_back(i);
arr[r].dists.push_back(t);
break;
}
}
}
return;
}
Compilation message
citymapping.cpp: In function 'void dfs(int, int, int, std::vector<node>&, std::vector<int>&, int)':
citymapping.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for(int i = 0; i < tree[head].childs.size(); i ++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Reported list of edges differ from actual. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Reported list of edges differ from actual. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Reported list of edges differ from actual. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Reported list of edges differ from actual. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Reported list of edges differ from actual. |
| 2 |
Halted |
0 ms |
0 KB |
- |
