#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
typedef long long ll;
const int N = 100001;
int A[N], B[N], W[N], n, depth[N];
vector<int> g[N];
bool used[N];
int pp[N], cnt[N];
void dfs(int v, int p) {
pp[v] = p;
for (int to: g[v]) {
if (to != p) {
depth[to] = depth[v] + 1;
dfs(to, v);
}
}
}
vector<ll> minimum_closure_costs(int nn, vector<int> uu, vector<int> vv, vector<int> ww) {
n = nn;
for (int i = 0; i < n - 1; ++i) {
A[i] = uu[i], B[i] = vv[i], W[i] = ww[i];
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
vector<ll> ans(n);
vector<int> ord(n);
iota(all(ord), 0);
sort(all(ord), [](int i, int j) {
return g[i].size() > g[j].size();
});
dfs(0, -1);
for (int k = 0; k < n; ++k) {
vector<int> now;
for (int i: ord) {
if (g[i].size() <= k) break;
now.push_back(i);
used[i] = true;
cnt[i] = g[i].size();
}
int cntt = 0;
for (int i : now) {
if (pp[i] != -1 && used[pp[i]]) {
--cnt[pp[i]];
--cnt[i];
++cntt;
}
}
for (int i : now) {
ans[k] += k - cnt[i];
used[i] = false;
}
ans[k] = cntt - ans[k];
}
return ans;
}
Compilation message
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:44:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | if (g[i].size() <= k) break;
| ~~~~~~~~~~~~^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
87 ms |
12104 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
87 ms |
12104 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |