| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 915359 |
2024-01-23T18:37:42 Z |
Alcabel |
Toll (APIO13_toll) |
C++17 |
|
1114 ms |
14072 KB |
#include <bits/stdc++.h>
using namespace std;
struct DSU {
int n;
vector<int> par, sz;
DSU() {}
DSU(int _n) {
n = _n;
par.resize(n);
sz.resize(n);
clear();
}
void clear() {
for (int i = 0; i < n; ++i) {
par[i] = i, sz[i] = 1;
}
}
int getParent(int v) {
if (par[v] != v) {
par[v] = getParent(par[v]);
}
return par[v];
}
bool uniteSets(int v, int u) {
v = getParent(v), u = getParent(u);
if (v == u) { return false; }
if (sz[v] < sz[u]) { swap(v, u); }
par[u] = v;
sz[v] += sz[u];
return true;
}
~DSU() {}
};
struct Edge {
int v, u, w;
Edge() {}
Edge(int _v, int _u, int _w) {
v = _v, u = _u, w = _w;
}
bool operator<(const Edge& other) const {
return w < other.w;
}
~Edge() {}
};
vector<vector<pair<int, int>>> g;
vector<int> h, parW, par;
vector<long long> compP, sumP;
void dfsPrecalc(int v) {
sumP[v] = compP[v];
for (const auto& [u, newW] : g[v]) {
if (u != par[v]) {
parW[u] = newW;
par[u] = v;
h[u] = h[v] + 1;
dfsPrecalc(u);
sumP[v] += sumP[u];
}
}
// cerr << "v: " << v << ", sumP: " << sumP[v] << ", compP: " << compP[v] << '\n';
}
void minEq(int v, int u, int w) {
if (h[v] < h[u]) {
swap(v, u);
}
while (h[v] > h[u]) {
parW[v] = min(parW[v], w);
v = par[v];
}
while (v != u) {
parW[v] = min(parW[v], w);
parW[u] = min(parW[u], w);
v = par[v], u = par[u];
}
}
long long dfsAns(int v) {
long long res = parW[v] * sumP[v];
for (const auto& [u, newW] : g[v]) {
if (u != par[v]) {
res += dfsAns(u);
}
}
return res;
}
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<Edge> edges(m);
for (int i = 0; i < m; ++i) {
int v, u, w;
cin >> v >> u >> w;
--v, --u;
edges[i] = Edge(v, u, w);
}
vector<Edge> additional(k);
DSU with(n);
for (int i = 0; i < k; ++i) {
int v, u;
cin >> v >> u;
--v, --u;
additional[i] = Edge(v, u, 1000001);
with.uniteSets(v, u);
}
vector<int> p(n);
for (int i = 0; i < n; ++i) {
cin >> p[i];
}
sort(edges.begin(), edges.end());
DSU without(n);
// cerr << "!\n";
vector<Edge> mstEdges;
for (int i = 0; i < m; ++i) {
if (without.uniteSets(edges[i].v, edges[i].u)) {
mstEdges.emplace_back(edges[i]);
}
}
// cerr << "!\n";
without.clear();
vector<Edge> sus;
for (const Edge& e : mstEdges) {
if (with.getParent(e.v) != with.getParent(e.u)) {
without.uniteSets(e.v, e.u);
} else {
sus.emplace_back(e);
}
with.uniteSets(e.v, e.u);
}
// cerr << "!\n";
assert((int)sus.size() <= k);
vector<int> compOf(n, -1);
int comps = 0;
for (int i = 0; i < n; ++i) {
if (compOf[without.getParent(i)] == -1) {
compOf[without.getParent(i)] = comps++;
compP.emplace_back(0);
}
int c = compOf[without.getParent(i)];
compOf[i] = c;
compP[c] += p[i];
}
g.resize(comps);
h.resize(comps);
sumP.resize(comps);
par.resize(comps);
parW.resize(comps);
for (Edge& e : sus) {
e.v = compOf[e.v];
e.u = compOf[e.u];
assert(e.v != e.u);
}
for (Edge& e : additional) {
e.v = compOf[e.v];
e.u = compOf[e.u];
assert(e.v != e.u);
}
long long ans = 0;
DSU comp(comps);
vector<Edge> limits;
/*cerr << "!\n";
for (int i = 0; i < n; ++i) {
cerr << "i: " << i << ", compOf: " << compOf[i] << '\n';
}*/
for (int mask = 1; mask < (1 << k); ++mask) {
comp.clear();
for (int i = 0; i < comps; ++i) {
g[i].clear();
}
bool hasCycle = false;
for (int i = 0; i < k; ++i) {
if (mask & (1 << i)) {
if (!comp.uniteSets(additional[i].v, additional[i].u)) {
hasCycle = true;
break;
}
g[additional[i].v].emplace_back(additional[i].u, additional[i].w);
g[additional[i].u].emplace_back(additional[i].v, additional[i].w);
}
}
if (hasCycle) {
continue;
}
// cerr << "mask: " << mask << ", dont have a cycle\n";
limits.clear();
for (const Edge& e : sus) {
if (comp.uniteSets(e.v, e.u)) {
g[e.v].emplace_back(e.u, 0);
g[e.u].emplace_back(e.v, 0);
} else {
limits.emplace_back(e);
}
}
h[compOf[0]] = 0;
par[compOf[0]] = -1;
parW[compOf[0]] = 0;
// cerr << "dfsPrecalc:\n";
dfsPrecalc(compOf[0]);
for (const Edge& e : limits) {
minEq(e.v, e.u, e.w);
}
ans = max(ans, dfsAns(compOf[0]));
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
2 ms |
604 KB |
Output is correct |
| 6 |
Correct |
2 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
2 ms |
604 KB |
Output is correct |
| 6 |
Correct |
2 ms |
604 KB |
Output is correct |
| 7 |
Correct |
116 ms |
14032 KB |
Output is correct |
| 8 |
Correct |
117 ms |
14072 KB |
Output is correct |
| 9 |
Correct |
117 ms |
14060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
2 ms |
604 KB |
Output is correct |
| 6 |
Correct |
2 ms |
604 KB |
Output is correct |
| 7 |
Correct |
116 ms |
14032 KB |
Output is correct |
| 8 |
Correct |
117 ms |
14072 KB |
Output is correct |
| 9 |
Correct |
117 ms |
14060 KB |
Output is correct |
| 10 |
Correct |
742 ms |
13808 KB |
Output is correct |
| 11 |
Correct |
1091 ms |
14008 KB |
Output is correct |
| 12 |
Correct |
1114 ms |
14024 KB |
Output is correct |
