| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 208880 |
2020-03-12T11:49:17 Z |
atoiz |
Toll (APIO13_toll) |
C++14 |
|
6 ms |
376 KB |
/*input
5 4 1
1 2 5
2 3 7
3 4 6
4 5 9
3 5
1 10 100 1000 10000
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cassert>
using namespace std;
const int MAXN = 1e5 + 6, MAXM = 3e5 + 5, MAXK = 102;
const int INF = 1e8;
struct edge_t
{
int u, v, c;
edge_t(int _u = 0, int _v = 0, int _c = 0):
u(_u), v(_v), c(_c) {}
};
struct dsu_t
{
int N;
vector<int> vec;
void init(int _N)
{
N = _N;
vec.resize(N + 1);
for (int i = 1; i <= N; ++i) vec[i] = -1;
}
int root(int x)
{
return (vec[x] < 0 ? x : vec[x] = root(vec[x]));
}
bool same(int x, int y)
{ return root(x) == root(y); }
void join(int x, int y)
{
x = root(x), y = root(y);
if (x == y) return;
if (vec[x] > vec[y]) swap(x, y);
vec[x] += vec[y];
vec[y] = x;
}
};
int N, M, K, C = 0;
int comp_id[MAXN];
int64_t P[MAXN], comp_weight[MAXK], subtree[MAXK];
vector<edge_t> edges, extra, comp_edges, copy_edges;
dsu_t comp_dsu;
int comp_dist[MAXK][MAXK];
bool weak_edge[MAXM];
vector<int> tree[MAXK];
template <typename T>
void minimize(T &x, T y)
{ x = (x < y ? x : y); }
template <typename T>
void maximize(T &x, T y)
{ x = (x > y ? x : y); }
void dfs_tree(int u, int p)
{
subtree[u] = comp_weight[u];
for (int v : tree[u]) {
if (v != p) {
dfs_tree(v, u);
subtree[u] += subtree[v];
}
}
}
void get_dist(int root, int u, int p, int mx)
{
comp_dist[root][u] = mx;
for (auto &e : comp_edges) {
int v = -1;
if (e.u == u) v = e.v;
else if (e.v == u) v = e.u;
else continue;
if (v != p) get_dist(root, v, u, max(mx, e.c));
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> K;
edges.resize(M);
for (auto &e : edges) cin >> e.u >> e.v >> e.c;
sort(edges.begin(), edges.end(), [&](edge_t &lhs, edge_t &rhs) { return lhs.c < rhs.c; });
extra.resize(K);
for (auto &e : extra) cin >> e.u >> e.v;
for (int i = 1; i <= N; ++i) cin >> P[i];
comp_dsu.init(N);
for (auto &e : extra) comp_dsu.join(e.u, e.v);
for (int i = 0; i < M; ++i) {
auto &e = edges[i];
if (not comp_dsu.same(e.u, e.v)) {
comp_dsu.join(e.u, e.v);
weak_edge[i] = true;
}
}
comp_dsu.init(N);
for (int i = 0; i < M; ++i) {
if (weak_edge[i]) {
comp_dsu.join(edges[i].u, edges[i].v);
}
}
for (int i = 1; i <= N; ++i) {
if (comp_dsu.root(i) == i) comp_id[i] = ++C;
}
for (int i = 1; i <= N; ++i) {
if (comp_dsu.root(i) != i) comp_id[i] = comp_id[comp_dsu.root(i)];
}
iota(comp_id + 1, comp_id + 1 + N, 1);
C = N;
// assert(C <= K + 1);
// for (int i = 1; i <= N; ++i) cout << "id " << i << ": " << comp_id[i] << endl;
for (auto &e : extra) e.u = comp_id[e.u], e.v = comp_id[e.v];
for (int i = 1; i <= N; ++i) {
comp_weight[comp_id[i]] += P[i];
}
// for (int i = 1; i <= C; ++i) cout << "weight " << i << ": " << comp_weight[i] << endl;
for (int u = 1; u <= C; ++u) {
for (int v = 1; v <= C; ++v) {
comp_dist[u][v] = INF;
}
}
for (auto &e : edges) {
minimize(comp_dist[comp_id[e.u]][comp_id[e.v]], e.c);
minimize(comp_dist[comp_id[e.v]][comp_id[e.u]], e.c);
}
for (int u = 2; u <= C; ++u) {
for (int v = 1; v < u; ++v) {
if (comp_dist[u][v] != INF) {
comp_edges.emplace_back(u, v, comp_dist[u][v]);
}
}
}
sort(comp_edges.begin(), comp_edges.end(), [&](edge_t &lhs, edge_t &rhs) { return lhs.c < rhs.c; });
comp_dsu.init(C);
for (auto &e : comp_edges) {
if (not comp_dsu.same(e.u, e.v)) {
copy_edges.push_back(e);
comp_dsu.join(e.u, e.v);
// cout << "edge " << e.u << ' ' << e.v << ": " << e.c << endl;
}
}
comp_edges = move(copy_edges);
for (int u = 1; u <= C; ++u) {
get_dist(u, u, u, -1);
}
for (auto &e : extra) e.c = comp_dist[e.u][e.v];
// for (auto &e : extra) cout << "extra " << e.u << ' ' << e.v << ": " << e.c << endl;
// return cout << extra[0].c * comp_weight[3 - comp_id[1]] << endl, 0;
int64_t optimal = 0;
for (int mask = 0; mask < (1 << K); ++mask) {
comp_dsu.init(C);
for (int i = 1; i <= C; ++i) tree[i].clear();
bool cycle = false;
for (int i = 0; i < K; ++i) if ((mask >> i) & 1) {
auto &e = extra[i];
if (comp_dsu.same(e.u, e.v)) {
cycle = true;
break;
}
comp_dsu.join(e.u, e.v);
tree[e.u].push_back(e.v);
tree[e.v].push_back(e.u);
}
if (cycle) continue;
for (auto &e : comp_edges) {
if (not comp_dsu.same(e.u, e.v)) {
comp_dsu.join(e.u, e.v);
tree[e.u].push_back(e.v);
tree[e.v].push_back(e.u);
}
}
dfs_tree(comp_id[1], 0);
int64_t total = 0;
for (int i = 0; i < K; ++i) if ((mask >> i) & 1) {
auto &e = extra[i];
total += e.c * min(subtree[e.u], subtree[e.v]);
}
// cout << "total " << mask << ": " << total << endl;
maximize(optimal, total);
}
cout << optimal << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
