| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 561849 |
2022-05-13T16:18:04 Z |
Cyanmond |
Toll (APIO13_toll) |
C++17 |
|
2500 ms |
12680 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 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);
vector<vector<int>> graph(N);
for (const auto &[cost, a, b] : E) {
if (uft.is_same(a, b)) continue;
uft.unite(a, b);
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<char> used(N);
vector<vector<int>> groups;
REP(i, N) {
if (used[i]) continue;
groups.push_back({});
auto dfs = [&](auto &&self, const int v) -> void {
used[v] = true;
groups.back().push_back(v);
for (const int t : graph[v]) {
if (used[t]) continue;
self(self, t);
}
};
dfs(dfs, 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;
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);
pair<int, int> tree[30][30];
int size_d[30];
// vector<pair<int, int>> tree[30];
i64 nec[30];
REP(bit, 1 << K) {
fill(begin(size_d), begin(size_d) + N, 0);
auto uft = uftb;
fill(begin(nec), begin(nec) + N, inf);
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][size_d[A[i].first]++] = {A[i].second, i};
tree[A[i].second][size_d[A[i].second]++] = {A[i].first, i};
}
}
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 {
REP(j, size_d[v]) {
const auto &[t, c] = tree[v][j];
if (t == p) continue;
if (t == E[i].b) {
chmin(nec[c], E[i].cost);
return true;
}
if (self(self, t, v)) {
chmin(nec[c], E[i].cost);
return true;
}
}
return false;
};
assert(dfs(dfs, E[i].a, -1));
} else {
uft.unite(E[i].a, E[i].b);
tree[E[i].a][size_d[E[i].a]++] = {E[i].b, -1};
tree[E[i].b][size_d[E[i].b]++] = {E[i].a, -1};
}
}
i64 res = 0;
auto dfs = [&](auto &&self, const int v, const int p) -> i64 {
i64 sum = 0;
REP(j, size_d[v]) {
const auto &[t, c] = tree[v][j];
if (t == p) continue;
const i64 e = self(self, t, v);
if (c != -1) res += nec[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 |
2 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 |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
6 ms |
380 KB |
Output is correct |
| 6 |
Correct |
6 ms |
376 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 |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
6 ms |
380 KB |
Output is correct |
| 6 |
Correct |
6 ms |
376 KB |
Output is correct |
| 7 |
Correct |
377 ms |
12680 KB |
Output is correct |
| 8 |
Correct |
442 ms |
12536 KB |
Output is correct |
| 9 |
Correct |
383 ms |
12672 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 |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
6 ms |
380 KB |
Output is correct |
| 6 |
Correct |
6 ms |
376 KB |
Output is correct |
| 7 |
Correct |
377 ms |
12680 KB |
Output is correct |
| 8 |
Correct |
442 ms |
12536 KB |
Output is correct |
| 9 |
Correct |
383 ms |
12672 KB |
Output is correct |
| 10 |
Correct |
1703 ms |
12664 KB |
Output is correct |
| 11 |
Execution timed out |
2557 ms |
12680 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
