#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];
set<int> deg[N];
set<pair<int, int>> e;
bool used[N], kid[N];
int cnt = 0, pp[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]);
e.insert(make_pair(A[i], B[i]));
}
vector<ll> ans(n);
ans[0] = 0;
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 = 1; k < n; ++k) {
vector<int> now;
for (int i: ord) {
if (g[i].size() < k - 1) break;
if (g[i].size() < k) {
for (int x: g[i]) {
if ((e.count({x, i}) || e.count({i, x})) && g[x].size() >= k) {
deg[x].insert(i);
}
}
continue;
}
now.push_back(i);
}
sort(all(now), [](int i, int j) {
return depth[i] > depth[j];
});
ans[k] = ans[k - 1];
for (int i: now) {
if (kid[i] || (pp[i] != -1 && kid[pp[i]])) continue;
for (int to : deg[i]) {
++ans[k];
e.erase({to, i});
e.erase({i, to});
kid[i] = true;
break;
}
if (!deg[i].empty()) {
deg[i].erase(begin(deg[i]));
}
}
for (int i: now) {
if (used[i] || pp[i] == -1 || kid[pp[i]] || kid[i]) continue;
used[i] = true;
kid[pp[i]] = true;
deg[i].erase(pp[i]);
deg[pp[i]].erase(i);
e.erase({i, pp[i]});
e.erase({pp[i], i});
++ans[k];
}
for (int i: now) {
if (pp[i] != -1) {
kid[pp[i]] = false;
}
kid[i] = false;
}
}
for (int i = 0; i < n; ++i) ans[i] = n - 1 - ans[i];
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:48:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
48 | if (g[i].size() < k - 1) break;
| ~~~~~~~~~~~~^~~~~~~
roads.cpp:49:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
49 | if (g[i].size() < k) {
| ~~~~~~~~~~~~^~~
roads.cpp:51:77: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
51 | if ((e.count({x, i}) || e.count({i, x})) && g[x].size() >= k) {
| ~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
376 ms |
21004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
376 ms |
21004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
