#ifndef Local
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse4,sse4.2,popcnt,abm,mmx,avx")
#endif
#include <bits/stdc++.h>
using namespace std;
#define popCnt(x) (__builtin_popcountll(x))
#define sz(x) ((int)(x.size()))
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
typedef long long Long;
typedef float Double;
template <class U, class V>
istream& operator>>(istream& is, pair<U, V>& p) {
is >> p.first >> p.second;
return is;
}
template <class T>
istream& operator>>(istream& is, vector<T>& v) {
for (auto& x : v) {
is >> x;
}
return is;
}
template <class T>
ostream& operator<<(ostream& os, vector<T>& v) {
for (auto& x : v) {
os << x << " ";
}
return os;
}
set<int> elements;
multiset<int> gaps;
void addElement(int x) {
auto nxt = elements.upper_bound(x);
bool is_last = (nxt == end(elements));
bool is_first = (nxt == begin(elements));
auto prv = nxt;
if (!is_first) --prv;
if (!is_last && !is_first) {
gaps.erase(gaps.find(*nxt - *prv));
}
if (!is_first) gaps.emplace(x - *prv);
if (!is_last) gaps.emplace(*nxt - x);
elements.emplace(x);
}
void eraseElement(int x) {
elements.erase(x);
auto nxt = elements.upper_bound(x);
bool is_last = (nxt == end(elements));
bool is_first = (nxt == begin(elements));
auto prv = nxt;
if (!is_first) --prv;
if (!is_last) {
gaps.erase(gaps.find(*nxt - x));
}
if (!is_first) {
gaps.erase(gaps.find(x - *prv));
}
if (!is_last && !is_first) {
gaps.emplace(*nxt - *prv);
}
}
int solve() {
if (elements.empty()) return 0;
return *elements.rbegin() - *elements.begin() - *gaps.rbegin();
}
const Double EPS = 1e-10;
enum Relation { LESS_THAN, EQUAL, GREATER_THAN };
bool areEqual(Double x, Double y, Double eps = EPS) {
auto diff = abs(x - y);
x = abs(x), y = abs(y);
if (diff <= eps) return true;
if (min(x, y) <= eps) return false;
return diff <= eps * max(x, y);
}
bool isZero(Double x, Double eps = EPS) { return abs(x) <= eps; }
bool isZero(Long x) { return x == 0; }
int compareDoubles(Double x, Double y, Double eps = EPS) {
if (areEqual(x, y, eps)) return Relation::EQUAL;
if (x < y) return Relation::LESS_THAN;
return Relation::GREATER_THAN;
}
template <typename T = Double>
struct Point {
typedef Point P;
const static P Invalid;
const static P Origin;
T x = 0, y = 0;
Point(T x, T y) : x(x), y(y) {}
Point() {}
pair<T, T> to_pair() const { return make_pair(x, y); }
Point operator+(const Point& p) const { return Point{x + p.x, y + p.y}; }
Point operator-(const Point& p) const { return Point{x - p.x, y - p.y}; }
Point operator*(T c) const { return Point(x * c, y * c); }
Point operator/(T c) const { return Point(x / c, y / c); }
bool operator<(const Point& p) const {
return (*this) != p && to_pair() < p.to_pair();
}
bool operator>(const Point& p) const { return (*this) != p && !(*this < p); }
bool operator==(const Point& p) const {
return isZero(this->x - p.x) && isZero(this->y - p.y);
}
bool operator!=(const Point& p) const { return !(*this == p); }
T cross(const P& p) const { return x * p.y - y * p.x; }
T cross(const P& a, const P& b) const { return (a - *this).cross(b - *this); }
T dot(const P& p) const { return x * p.x + y * p.y; }
P midPoint(const P& p) const { return ((*this) + p) / 2; }
P getVector(const P& p) const { return p - (*this); }
T dist2(const P& p) const { return getVector(p).dist2(); }
T dist2() const { return (*this).dot(*this); }
Double dist(const P& p) const { return sqrt(dist2(p)); }
Double dist() const { return sqrt(dist2()); }
friend istream& operator>>(istream& is, P& p) { return is >> p.x >> p.y; }
friend ostream& operator<<(ostream& os, const P& p) {
return os << p.x << " " << p.y;
}
};
template <typename T>
const Point<T> Point<T>::Invalid = Point<T>(numeric_limits<T>::max(),
numeric_limits<T>::max());
template <typename T>
const Point<T> Point<T>::Origin = Point<T>(0, 0);
typedef Point<Double> P;
const int N = 200;
struct DSU {
int parent[N];
void init() {
for (int i = 0; i < N; ++i) {
parent[i] = i;
}
}
int getRoot(int x) {
if (parent[x] == x) return x;
return parent[x] = getRoot(parent[x]);
}
bool join(int x, int y) {
x = getRoot(x);
y = getRoot(y);
if (x == y) return false;
parent[x] = y;
return true;
}
};
struct Edge {
int u, v;
int t, c;
};
vector<Edge> edges;
struct Solution {
uint t = 0, c = 0;
vector<int> edges;
uint score() const { return t * c; }
bool operator<(const Solution& other) const {
return score() < other.score();
}
bool operator==(const Solution& other) const {
return t == other.t && c == other.c;
}
};
Solution mst(const P& coeff) {
vector<int> edge_inds(sz(edges));
iota(all(edge_inds), 0);
sort(all(edge_inds), [&](int i, int j) {
return coeff.x * edges[i].t + coeff.y * edges[i].c <
coeff.x * edges[j].t + coeff.y * edges[j].c;
});
static DSU dsu;
dsu.init();
Solution sol;
for (int edge_ind : edge_inds) {
auto& edge = edges[edge_ind];
if (dsu.join(edge.u, edge.v)) {
sol.t += edge.t, sol.c += edge.c;
sol.edges.emplace_back(edge_ind);
}
}
return sol;
}
Solution best;
void solve(const P& left_v, const P& right_v, const Solution& left_sol,
const Solution& right_sol) {
if (left_sol == right_sol || left_v.dist2(right_v) < 1e-7) return;
P mid = left_v.midPoint(right_v);
auto sol = mst(mid);
best = min(best, sol);
solve(left_v, mid, left_sol, sol);
solve(mid, right_v, sol, right_sol);
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef Local
freopen("test.in", "r", stdin);
#else
#define endl '\n'
#endif
int n, m;
cin >> n >> m;
edges.resize(m);
for (auto& edge : edges) {
cin >> edge.u >> edge.v >> edge.t >> edge.c;
}
P left_v(0, 1);
P right_v(1, 0);
auto left_sol = mst(left_v);
auto right_sol = mst(right_v);
best = min(left_sol, right_sol);
solve(left_v, right_v, left_sol, right_sol);
cout << best.t << " " << best.c << endl;
for (int ind : best.edges) {
cout << edges[ind].u << " " << edges[ind].v << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
8 ms |
512 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
37 ms |
384 KB |
Output is correct |
| 15 |
Correct |
25 ms |
384 KB |
Output is correct |
| 16 |
Correct |
538 ms |
504 KB |
Output is correct |
| 17 |
Correct |
577 ms |
504 KB |
Output is correct |
| 18 |
Correct |
545 ms |
504 KB |
Output is correct |
| 19 |
Execution timed out |
2088 ms |
512 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2090 ms |
512 KB |
Time limit exceeded |
