#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pii = pair<int, int>;
//BeginCodeSnip{DSU}
struct DSU {
vector<int> g;
DSU(int n) : g(n, -1) {}
int find(int a) { return g[a] < 0 ? a : (g[a] = find(g[a])); }
/**
* If a and b are already in the same set, return false and do nothing.
* Otherwise, merge set a and b into one set and return true.
*/
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (g[a] > g[b]) swap(a, b);
g[a] += g[b];
g[b] = a;
return true;
}
};
//EndCodeSnip
struct Edge {
int x;
int y;
int time;
int cost;
int id;
};
/**
* Kruskal's Algorithm to find a MST with given edges and weights. Returns the
* time and cost as pair<int,int> as well as ids of edges of the MST as
* vector<int>.
*/
pair<pii, vector<int>> kruskal(
int n, vector<Edge> &edges, vector<int> &weights
) {
sort(begin(edges), end(edges), [&](const Edge &e1, const Edge &e2) {
return weights[e1.id] < weights[e2.id];
});
DSU dsu(n);
vector<int> mst;
int t = 0;
int c = 0;
for (Edge &e : edges) {
if (dsu.unite(e.x, e.y)) {
t += e.time;
c += e.cost;
mst.push_back(e.id);
}
}
return {{t, c}, mst};
}
/**
* Calculate the signed area of the triangle defined by the given points.
* This value is negative if point P is on the right side of vector AB.
*/
ll area(pii A, pii B, pii P) {
pii AB = {B.first - A.first, B.second - A.second};
pii AP = {P.first - A.first, P.second - A.second};
return AB.first * AP.second - AB.second * AP.first;
}
int main() {
int N, M;
cin >> N >> M;
vector<Edge> edges(M);
for (int i = 0; i < M; i++) {
int x, y, t, c;
cin >> x >> y >> t >> c;
edges[i] = {x, y, t, c, i};
}
// The best Minimum Spanning Tree found so far.
vector<int> best_MST;
// The sum of time and cost w.r.t. best_MST.
pii best_V = {1e8, 1e8};
vector<int> current_MST;
pii A, B, P;
// The weights used by Kruskal's Algorithm to determine the MST.
vector<int> weights(M);
// A corresponds to the values of the MST if we only minimize the time
for (int i = 0; i < M; i++) {
weights[edges[i].id] = edges[i].time;
}
tie(A, best_MST) = kruskal(N, edges, weights);
best_V = A;
// B corresponds to values of the MST if we only minimize the cost
for (int i = 0; i < M; i++) {
weights[edges[i].id] = edges[i].cost;
}
tie(B, current_MST) = kruskal(N, edges, weights);
// If solution B is better than A, update the best solution
if ((ll)B.first * B.second < (ll)A.first * A.second) {
best_V = B;
best_MST = current_MST;
}
// Search recursively for points on lower convex hull of the solution space
stack<pair<pii, pii>> to_search;
to_search.push({A, B});
while (!to_search.empty()) {
auto [A, B] = to_search.top();
to_search.pop();
/*
* Since P is on the right side of vector AB, the signed area is negative.
* Thus, to maximize the unsigned area of triangle ABP, we should minimize
* this signed value.
*/
for (int i = 0; i < M; i++) {
weights[edges[i].id] = (
edges[i].cost * (B.first - A.first) -
edges[i].time * (B.second - A.second)
);
}
tie(P, current_MST) = kruskal(N, edges, weights);
/*
* If P is on the left side of vector AB, we can terminate the search
* on this branch. Note that the "left side of vector AB" is the right side
* on the coordinate system.
*/
if (area(A, B, P) >= 0) {
continue;
}
// Compare the V value and update the best result if needed.
if ((ll)P.first * P.second < (ll)best_V.first * best_V.second) {
best_V = P;
best_MST = current_MST;
}
/*
* Search further with the new acquired point P to see if there is another
* point that is on a hyperbola further left than P.
*/
to_search.push({A, P});
to_search.push({P, B});
}
cout << best_V.first << " " << best_V.second << "\n";
sort(begin(edges), end(edges),
[](const Edge &e1, const Edge &e2) { return e1.id < e2.id; });
for (int &id : best_MST) {
cout << edges[id].x << " " << edges[id].y << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
296 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Correct |
2 ms |
340 KB |
Output is correct |
| 8 |
Correct |
9 ms |
596 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
300 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
4 ms |
300 KB |
Output is correct |
| 15 |
Correct |
3 ms |
212 KB |
Output is correct |
| 16 |
Correct |
45 ms |
356 KB |
Output is correct |
| 17 |
Correct |
49 ms |
340 KB |
Output is correct |
| 18 |
Correct |
47 ms |
340 KB |
Output is correct |
| 19 |
Correct |
405 ms |
668 KB |
Output is correct |
| 20 |
Correct |
434 ms |
668 KB |
Output is correct |
