Submission #300081

#TimeUsernameProblemLanguageResultExecution timeMemory
300081Mohammad_Yassertimeismoney (balkan11_timeismoney)C++14
90 / 100
2086 ms640 KiB
#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 double 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 = 201; 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 timeMemoryGrader output
Fetching results...