| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 374184 |
2021-03-06T20:40:56 Z |
dolphingarlic |
Toll (APIO13_toll) |
C++14 |
|
2500 ms |
23132 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, m, k;
int u[300021], v[300021];
ll c[300021], p[100001];
int cmp1[100001], cmp2[100001];
int find(int A, int *cmp) { return (A == cmp[A] ? A : cmp[A] = find(cmp[A], cmp)); }
void onion(int A, int B, int *cmp) { cmp[find(A, cmp)] = find(B, cmp); }
vector<int> compressed;
vector<pair<int, ll>> graph[100001];
int root;
vector<tuple<ll, int, int>> critical;
bool assign(int node, int dest, ll weight, int parent = 0) {
if (node == dest) return true;
bool good = false;
for (int i = 0; i < graph[node].size(); i++)
if (graph[node][i].first != parent) {
if (assign(graph[node][i].first, dest, weight, node)) {
good = true;
if (graph[node][i].second == -1)
graph[node][i].second = weight;
}
}
return good;
}
pair<ll, ll> calc(int node, int parent = 0) {
pair<ll, ll> ans = {0, p[node]};
for (pair<int, ll> i : graph[node]) if (i.first != parent) {
pair<ll, ll> tmp = calc(i.first, node);
ans.first += tmp.first + tmp.second * i.second;
ans.second += tmp.second;
}
return ans;
}
ll check(int mask) {
// Reset the graph and the DSU
for (int i : compressed) graph[i].clear(), cmp2[i] = i;
// Onion stuff based on mask, and construct some edges in the graph
for (int i = 1; i <= k; i++) if (mask & (1 << i - 1)) {
if (find(u[m + i], cmp2) == find(v[m + i], cmp2)) return 0;
graph[u[m + i]].push_back({v[m + i], -1});
graph[v[m + i]].push_back({u[m + i], -1});
onion(u[m + i], v[m + i], cmp2);
}
for (auto i : critical) {
if (find(get<1>(i), cmp2) == find(get<2>(i), cmp2)) {
// Assign weights to edges on the path between these two nodes
assign(get<1>(i), get<2>(i), get<0>(i));
assign(get<2>(i), get<1>(i), get<0>(i));
} else {
// Add an edge to the graph
graph[get<1>(i)].push_back({get<2>(i), 0});
graph[get<2>(i)].push_back({get<1>(i), 0});
onion(get<1>(i), get<2>(i), cmp2);
}
}
return calc(root).first;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> c[i];
for (int i = 1; i <= k; i++) cin >> u[m + i] >> v[m + i];
for (int i = 1; i <= n; i++) cin >> p[i];
// Find the mandatory edges and collapse components together
vector<tuple<ll, int, int>> edges;
for (int i = 1; i <= m + k; i++) edges.push_back({c[i], u[i], v[i]});
sort(edges.begin(), edges.end());
iota(cmp1 + 1, cmp1 + n + 1, 1);
iota(cmp2 + 1, cmp2 + n + 1, 1);
for (auto i : edges) {
if (find(get<1>(i), cmp1) != find(get<2>(i), cmp1)) {
if (get<0>(i)) {
p[find(get<2>(i), cmp2)] += p[find(get<1>(i), cmp2)];
onion(get<1>(i), get<2>(i), cmp2);
}
onion(get<1>(i), get<2>(i), cmp1);
}
}
// Find the K + 1 component parents and the root after compression
for (int i = 1; i <= n; i++) {
cmp1[i] = cmp2[i];
if (i == cmp2[i]) compressed.push_back(i);
}
root = find(1, cmp2);
// Find the K "critical" edges
for (auto i : edges) {
if (get<0>(i) && find(get<1>(i), cmp1) != find(get<2>(i), cmp1)) {
critical.push_back(i);
onion(get<1>(i), get<2>(i), cmp1);
}
}
for (int i = 1; i <= n; i++) cmp1[i] = cmp2[i];
// Re-index
for (int i = 1; i <= k; i++) u[m + i] = find(u[m + i], cmp1), v[m + i] = find(v[m + i], cmp1);
for (auto& i : critical) get<1>(i) = find(get<1>(i), cmp1), get<2>(i) = find(get<2>(i), cmp1);
// Test each subset of edges
ll ans = 0;
for (int mask = 1; mask < (1 << k); mask++) ans = max(ans, check(mask));
cout << ans;
return 0;
}
Compilation message
toll.cpp: In function 'bool assign(int, int, ll, int)':
toll.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for (int i = 0; i < graph[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~
toll.cpp: In function 'll check(int)':
toll.cpp:47:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
47 | for (int i = 1; i <= k; i++) if (mask & (1 << i - 1)) {
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2668 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2668 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2668 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3052 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2668 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2668 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3052 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3052 KB |
Output is correct |
| 7 |
Correct |
223 ms |
23028 KB |
Output is correct |
| 8 |
Correct |
274 ms |
22952 KB |
Output is correct |
| 9 |
Correct |
268 ms |
23132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2668 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2668 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3052 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3052 KB |
Output is correct |
| 7 |
Correct |
223 ms |
23028 KB |
Output is correct |
| 8 |
Correct |
274 ms |
22952 KB |
Output is correct |
| 9 |
Correct |
268 ms |
23132 KB |
Output is correct |
| 10 |
Execution timed out |
2572 ms |
23008 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
