| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 561812 |
2022-05-13T15:17:40 Z |
Cyanmond |
Toll (APIO13_toll) |
C++17 |
|
2500 ms |
19348 KB |
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
constexpr i64 inf = 1ll << 60;
#define REP(i, n) for (int i = 0; i < (n); ++i)
template <typename T> void chmax(T &a, const T b) {
if (a < b) a = b;
}
template <typename T> void chmin(T &a, const T b) {
if (a > b) a = b;
}
struct UnionFind {
int n;
vector<int> data;
UnionFind(const int n_) : n(n_), data(n, -1) {}
int find(int v) {
if (data[v] < 0)
return v;
else
return data[v] = find(data[v]);
}
int is_same(int a, int b) { return find(a) == find(b); }
int size(int v) { return -data[find(v)]; }
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (size(a) < size(b)) swap(a, b);
data[a] += data[b];
data[b] = a;
}
};
struct Merger {
int n;
vector<int> roots;
vector<vector<int>> vals;
Merger(const int n_) {
n = n_;
roots.assign(n, -1);
REP(i, n) vals.push_back({i});
}
int find(int a) {
if (roots[a] < 0)
return a;
else
return roots[a] = find(roots[a]);
}
int size(int v) { return -roots[find(v)]; }
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (size(a) < size(b)) swap(a, b);
for (const int e : vals[b]) vals[a].push_back(e);
roots[a] += roots[b];
roots[b] = a;
}
};
struct Edge {
i64 cost;
int a;
int b;
};
int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
int N, M, K;
cin >> N >> M >> K;
vector<Edge> E(M);
REP(i, M) {
cin >> E[i].a >> E[i].b >> E[i].cost;
--E[i].a, --E[i].b;
}
vector<pair<int, int>> A(K);
for (auto &[x, y] : A) {
cin >> x >> y;
--x, --y;
}
vector<i64> P(N);
for (auto &e : P) cin >> e;
sort(E.begin(), E.end(), [](Edge a, Edge b) { return a.cost < b.cost; });
{
UnionFind uft(N);
REP(i, K) uft.unite(A[i].first, A[i].second);
Merger mt(N);
for (const auto &[cost, a, b] : E) {
if (uft.is_same(a, b)) continue;
uft.unite(a, b);
mt.merge(a, b);
}
vector<bool> used(N);
vector<vector<int>> groups;
REP(i, N) {
if (used[mt.find(i)]) continue;
used[mt.find(i)] = true;
groups.push_back(mt.vals[mt.find(i)]);
}
const int L = (int)size(groups);
for (auto &g : groups) sort(g.begin(), g.end());
sort(groups.begin(), groups.end(), [](auto &a, auto &b) { return a[0] < b[0]; });
vector<int> att(N);
REP(i, L) {
const auto &g = groups[i];
for (const int e : g) att[e] = i;
}
vector<i64> NP(L);
REP(i, N) NP[att[i]] += P[i];
P = move(NP);
for (auto &[x, y] : A) {
x = att[x];
y = att[y];
}
REP(i, M) {
E[i].a = att[E[i].a];
E[i].b = att[E[i].b];
}
vector<Edge> E2;
for (const auto &[cost, a, b] : E)
if (a != b) E2.push_back({cost, a, b});
E = E2;
E2.clear();
uft = UnionFind(L);
for (const auto &[cost, a, b] : E) {
if (uft.is_same(a, b)) continue;
uft.unite(a, b);
E2.push_back({cost, a, b});
}
E = move(E2);
N = L;
M = (int)size(E);
}
i64 ans = 0;
UnionFind uftb(N);
REP(bit, 1 << K) {
vector<vector<pair<int, i64>>> tree(N);
auto uft = uftb;
bool possible = true;
REP(i, K) {
if (bit & (1 << i)) {
if (uft.is_same(A[i].first, A[i].second)) {
possible = false;
break;
}
uft.unite(A[i].first, A[i].second);
tree[A[i].first].push_back({A[i].second, inf});
tree[A[i].second].push_back({A[i].first, inf});
}
}
if (not possible) continue;
REP(i, M) {
if (uft.is_same(E[i].a, E[i].b)) {
auto dfs = [&](auto &&self, const int v, const int p) -> bool {
for (auto &[t, c] : tree[v]) {
if (t == p) continue;
if (t == E[i].b) {
chmin(c, E[i].cost);
return true;
}
if (self(self, t, v)) {
chmin(c, E[i].cost);
return true;
}
}
return false;
};
assert(dfs(dfs, E[i].a, -1));
swap(E[i].a, E[i].b);
assert(dfs(dfs, E[i].a, -1));
swap(E[i].a, E[i].b);
} else {
uft.unite(E[i].a, E[i].b);
tree[E[i].a].push_back({E[i].b, 0});
tree[E[i].b].push_back({E[i].a, 0});
}
}
i64 res = 0;
auto dfs = [&](auto &&self, const int v, const int p) -> i64 {
i64 sum = 0;
for (const auto &[t, c] : tree[v]) {
if (t == p) continue;
const i64 e = self(self, t, v);
if (c != 0) res += c * e;
sum += e;
}
return sum + P[v];
};
dfs(dfs, 0, -1);
chmax(ans, res);
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
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 |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
6 ms |
468 KB |
Output is correct |
| 6 |
Correct |
6 ms |
592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
6 ms |
468 KB |
Output is correct |
| 6 |
Correct |
6 ms |
592 KB |
Output is correct |
| 7 |
Correct |
404 ms |
14120 KB |
Output is correct |
| 8 |
Correct |
450 ms |
19348 KB |
Output is correct |
| 9 |
Correct |
427 ms |
16892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
6 ms |
468 KB |
Output is correct |
| 6 |
Correct |
6 ms |
592 KB |
Output is correct |
| 7 |
Correct |
404 ms |
14120 KB |
Output is correct |
| 8 |
Correct |
450 ms |
19348 KB |
Output is correct |
| 9 |
Correct |
427 ms |
16892 KB |
Output is correct |
| 10 |
Execution timed out |
2590 ms |
14200 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
