| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 563520 |
2022-05-17T11:51:14 Z |
KoD |
Toll (APIO13_toll) |
C++17 |
|
1655 ms |
12596 KB |
#include <bits/stdc++.h>
using ll = long long;
using std::vector;
using std::array;
using std::pair;
using std::tuple;
struct UnionFind {
vector<int> data;
UnionFind(const int n) : data(n, -1) {}
int find(const int u) {
return data[u] < 0 ? u : data[u] = find(data[u]);
}
bool merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) {
return false;
}
if (data[u] > data[v]) {
std::swap(u, v);
}
data[u] += data[v];
data[v] = u;
return true;
}
vector<vector<int>> groups() {
const int n = data.size();
vector<vector<int>> ret(n);
for (int i = 0; i < n; ++i) {
ret[find(i)].push_back(i);
}
const auto itr = std::remove_if(ret.begin(), ret.end(), [&](const std::vector<int>& v) { return v.empty(); });
ret.erase(itr, ret.end());
return ret;
}
void clear() {
std::fill(data.begin(), data.end(), -1);
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M, K;
std::cin >> N >> M >> K;
const auto edges = [&] {
vector<tuple<int, int, int>> all(M);
for (auto& [c, a, b] : all) {
std::cin >> a >> b >> c;
a -= 1, b -= 1;
}
std::sort(all.begin(), all.end());
vector<tuple<int, int, int>> ret;
ret.reserve(N - 1);
UnionFind dsu(N);
for (const auto& [c, a, b] : all) {
if (dsu.merge(a, b)) {
ret.emplace_back(a, b, c);
}
}
return ret;
}();
vector<pair<int, int>> add(K);
UnionFind add_only(N);
for (auto& [a, b] : add) {
std::cin >> a >> b;
a -= 1, b -= 1;
add_only.merge(a, b);
}
vector<int> pop(N);
for (auto& x : pop) {
std::cin >> x;
}
ll ans = 0;
UnionFind compress(N);
vector<tuple<int, int, int>> important;
for (const auto& [a, b, c] : edges) {
if (add_only.merge(a, b)) {
compress.merge(a, b);
} else {
important.emplace_back(a, b, c);
}
}
const auto groups = compress.groups();
const int G = groups.size();
vector<int> id(N);
vector<ll> pop_sum(G);
for (int i = 0; i < G; ++i) {
for (const int u : groups[i]) {
id[u] = i;
pop_sum[i] += pop[u];
}
}
for (auto& [a, b] : add) {
a = id[a], b = id[b];
}
for (auto& [a, b, c] : important) {
a = id[a], b = id[b];
}
UnionFind dsu(G);
vector<vector<int>> graph(G);
vector<tuple<int, int, int>> bad;
vector<int> par(G, -1), dep(G), cost(G);
vector<ll> sub(G);
for (int set = 0; set < (1 << K); ++set) {
[&] {
dsu.clear();
for (auto& v : graph) {
v.clear();
}
for (int i = 0; i < K; ++i) {
if (set >> i & 1) {
const auto& [a, b] = add[i];
if (!dsu.merge(a, b)) {
return;
}
graph[a].push_back(b);
graph[b].push_back(a);
}
}
bad.clear();
for (const auto& [a, b, c] : important) {
if (dsu.merge(a, b)) {
graph[a].push_back(b);
graph[b].push_back(a);
} else {
bad.emplace_back(a, b, c);
}
}
std::fill(par.begin(), par.end(), -1);
auto setup = [&](auto&& self, const int u) -> void {
sub[u] = pop_sum[u];
for (const int v : graph[u]) {
if (v != par[u]) {
par[v] = u;
dep[v] = dep[u] + 1;
self(self, v);
sub[u] += sub[v];
}
}
};
setup(setup, id[0]);
std::fill(cost.begin(), cost.end(), 0);
for (int i = 0; i < K; ++i) {
if (set >> i & 1) {
auto& [a, b] = add[i];
if (dep[a] > dep[b]) {
std::swap(a, b);
}
cost[b] = 1000000;
}
}
for (auto [a, b, c] : bad) {
while (a != b) {
if (dep[a] > dep[b]) {
cost[a] = std::min(cost[a], c);
a = par[a];
} else {
cost[b] = std::min(cost[b], c);
b = par[b];
}
}
}
ll sum = 0;
for (int i = 0; i < K; ++i) {
if (set >> i & 1) {
const int b = add[i].second;
sum += cost[b] * sub[b];
}
}
ans = std::max(ans, sum);
}();
}
std::cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
3 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
3 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
340 KB |
Output is correct |
| 7 |
Correct |
151 ms |
5852 KB |
Output is correct |
| 8 |
Correct |
153 ms |
6024 KB |
Output is correct |
| 9 |
Correct |
169 ms |
6196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
3 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
340 KB |
Output is correct |
| 7 |
Correct |
151 ms |
5852 KB |
Output is correct |
| 8 |
Correct |
153 ms |
6024 KB |
Output is correct |
| 9 |
Correct |
169 ms |
6196 KB |
Output is correct |
| 10 |
Correct |
1232 ms |
5888 KB |
Output is correct |
| 11 |
Correct |
1655 ms |
12560 KB |
Output is correct |
| 12 |
Correct |
1643 ms |
12596 KB |
Output is correct |
