| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 257332 |
2020-08-04T06:21:12 Z |
ttnhuy313 |
Toll (APIO13_toll) |
C++14 |
|
2 ms |
400 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct dsu_t {
int n;
vector <int> lab;
dsu_t() {}
dsu_t(int _n) {
this -> n = _n;
lab.assign(n + 5, -1);
}
int root(int x) {
return lab[x] == -1 ? x : lab[x] = root(lab[x]);
}
bool merge(int u, int v) {
int x = root(u), y = root(v);
if (x == y) return false;
lab[x] = y;
return true;
}
};
const int N = 1e5 + 5;
int n, m, k, r[N], sum[N], p[33], h[33], w[33];
array <int, 3> e[N];
array <int, 2> d[N];
vector <int> b, adj[33];
void dfs1(int u, int pre = -1) {
if (~pre) p[u] = pre, h[u] = h[pre] + 1;
else h[u] = 0, p[u] = 0;
for (int v : adj[u]) if (v != pre)
dfs1(v, u);
}
int dfs2(int u, int dd = 0) {
int r = dd * sum[u];
for (int v : adj[u]) if (v != p[u]) {
r += dfs2(v, dd + w[v]);
}
return r;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> k;
dsu_t d1(n), d2(n), d3(n);
for (int i = 1; i <= m; ++i) {
cin >> e[i][1] >> e[i][2] >> e[i][0];
}
sort(e + 1, e + 1 + m);
for (int i = 1; i <= k; ++i) {
cin >> d[i][0] >> d[i][1];
d1.merge(d[i][0], d[i][1]);
}
for (int i = 1; i <= m; ++i) {
if (!d2.merge(e[i][1], e[i][2]))
continue;
if (d1.merge(e[i][1], e[i][2])) d3.merge(e[i][1], e[i][2]);
else {
b.push_back(i);
}
}
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (d3.root(i) == i) r[i] = ++cnt;
}
for (int i = 1; i <= n; ++i) {
int si;
cin >> si;
sum[r[d3.root(i)]] += si;
}
for (int i = 1; i <= k; ++i) {
d[i][0] = r[d3.root(d[i][0])];
d[i][1] = r[d3.root(d[i][1])];
}
for (int bi : b) {
e[bi][1] = r[d3.root(e[bi][1])];
e[bi][2] = r[d3.root(e[bi][2])];
}
int ans = 0;
for (int mask = 0; mask < (1 << k); ++mask) {
for (int i = 1; i <= cnt; ++i)
adj[i].clear();
dsu_t d4(cnt), d5(cnt);
for (int i = 1; i <= k; ++i) if (mask & (1 << (i - 1))) if (d4.merge(d[i][0], d[i][1])) {
adj[d[i][0]].push_back(d[i][1]);
adj[d[i][1]].push_back(d[i][0]);
}
deque <array <int, 3>> dq; dq.clear();
for (int bi : b) {
if (d4.merge(e[bi][1], e[bi][2])) {
adj[e[bi][1]].push_back(e[bi][2]);
adj[e[bi][2]].push_back(e[bi][1]);
dq.push_front({0, e[bi][1], e[bi][2]});
} else dq.push_back(e[bi]);
}
dfs1(r[d3.root(1)]);
for (array <int, 3> ci : dq) {
int u = ci[1], v = ci[2];
while (u != v) {
if (h[u] < h[v]) swap(u, v);
w[u] = ci[0];
d5.merge(u, p[u]);
u = d5.root(u);
}
}
ans = max(ans, dfs2(r[d3.root(1)]));
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
400 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
400 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
400 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
400 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
