| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1096210 |
2024-10-04T05:54:56 Z |
xnqs |
Toll (APIO13_toll) |
C++17 |
|
0 ms |
344 KB |
// the idea is to maximize the number of red edges
// and at the same time maximize their cost,
// and because q is small, we can just iterate over every subset of red edges.
// now that i think about it, it's probably solvable in O(logN*2^q) but idk
// (there's a solution that optimizes this with link cut trees or euler tour trees for sure but thats probably overkill)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <functional>
class DSU {
private:
int n;
std::vector<int> t;
std::vector<int> sz;
public:
DSU(int n): n(n) {
t.assign(n,0); std::iota(t.begin(),t.end(),0);
sz.assign(n,1);
}
int Find(int k) {
return ((t[k]==k) ? k : t[k] = Find(t[k]));
}
int Unite(int a, int b) {
int ra = Find(a);
int rb = Find(b);
if (ra==rb) {
return 0;
}
if (sz[ra]<sz[rb]) {
std::swap(ra,rb);
}
sz[ra] += sz[rb];
t[rb] = ra;
return 1;
}
};
int gs, edg, q;
int node_val[5005];
std::vector<std::vector<std::pair<int,int>>> adj_list;
std::vector<std::vector<std::pair<int,int>>> adj_list_mst;
std::vector<std::vector<std::tuple<int,int,int>>> adj_list_new_tree;
std::vector<std::tuple<int,int,int>> black_edges;
std::vector<std::pair<int,int>> red_edges;
void build_mst() {
adj_list_mst.resize(gs+1);
std::sort(black_edges.begin(),black_edges.end(),[](const std::tuple<int,int,int>& a, const std::tuple<int,int,int>& b) {
return std::get<2>(a) < std::get<2>(b);
});
DSU dsu(gs+1);
for (const auto& [a, b, c] : black_edges) {
if (dsu.Unite(a,b)) {
adj_list_mst[a].emplace_back(b,c);
adj_list_mst[b].emplace_back(a,c);
}
}
}
std::tuple<int,int,int> most_expensive_edge_on_path(int src, int dest) {
std::vector<int> root(gs+1,-1);
std::vector<std::tuple<int,int,int>> max(gs+1, std::tuple<int,int,int>(-1,-1,-1));
std::queue<int> q;
q.emplace(src);
root[src] = 0;
q.emplace(dest);
root[dest] = 1;
std::tuple<int,int,int> ret(-1,-1,-1);
while (!q.empty()) {
int k = q.front();
q.pop();
for (const auto& [i, w, t] : adj_list_new_tree[k]) {
if (root[i]==-1) {
root[i] = root[k];
max[i] = std::max(max[i], ((!t) ? std::tuple<int,int,int>(w,k,i) : std::tuple<int,int,int>()));
}
else if (root[i]!=root[k]) {
ret = std::max(std::max(max[i], max[k]), ((!t) ? std::tuple<int,int,int>(w,k,i) : std::tuple<int,int,int>()));
break;
}
}
}
return ret;
}
// ok, so first we build the mst of the black edges.
// then, we iterate over the set of selected red edges, and we try to insert them into
// the new cycle in the mst that gets created and break it at the most expensive non-red edge.
// the weight of the red edge now becomes the weight of the most expensive black edge along the path.
int64_t solve(int mask) {
adj_list_new_tree.clear();
adj_list_new_tree.resize(gs+1);
for (int i = 1; i <= gs; i++) {
for (const auto& [j, w] : adj_list_mst[i]) {
adj_list_new_tree[i].emplace_back(j,w,0);
}
}
for (int i = 0; i < mask; i++) {
if (mask&(1<<i)) {
auto [u, v] = red_edges[i];
auto [w, a, b] = most_expensive_edge_on_path(u, v);
if (w==-1) {
continue;
}
adj_list_new_tree[a].erase(std::find(adj_list_new_tree[a].begin(),adj_list_new_tree[a].end(),std::tuple<int,int,int>(b,w,0)));
adj_list_new_tree[b].erase(std::find(adj_list_new_tree[b].begin(),adj_list_new_tree[b].end(),std::tuple<int,int,int>(a,w,0)));
adj_list_new_tree[u].emplace_back(v,w,1);
adj_list_new_tree[v].emplace_back(u,w,1);
}
}
std::vector<int64_t> sub_sz(gs+1,0);
const std::function<int64_t(int,int)> dfs = [&](int k, int p) {
int64_t ret = 0;
sub_sz[k] = node_val[k];
for (const auto& [i, w, t] : adj_list_new_tree[k]) {
if (i!=p) {
ret = std::max(ret, dfs(i,k));
sub_sz[k] += sub_sz[i];
if (t) {
ret = std::max(ret, (int64_t)w*sub_sz[i]);
}
}
}
return ret;
};
return dfs(1,0);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> gs >> edg >> q;
adj_list.resize(gs+1);
for (int i = 0, a, b, c; i < edg; i++) {
std::cin >> a >> b >> c;
black_edges.emplace_back(a,b,c);
}
for (int i = 0, a, b; i < q; i++) {
std::cin >> a >> b;
red_edges.emplace_back(a,b);
}
for (int i = 1; i <= gs; i++) {
std::cin >> node_val[i];
}
build_mst();
int64_t ans = 0;
for (int mask = 1; mask < (1<<q); mask++) {
ans = std::max(ans, solve(mask));
}
std::cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
