Submission #302433

#	Time	Username	Problem	Language	Result	Execution time	Memory
302433		Mohammad_Yasser	timeismoney (balkan11_timeismoney)	C++14	100 / 100	157 ms	1280 KiB

timeismoney

#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;
}

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()); }
  P rotateCCW90() const { return P(-y, x); }
  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<Long> P;

bool areCollinear(const P& a, const P& b, const P& c) {
  return isZero(a.getVector(b).cross(c.getVector(b)));
}

const int N = 200;

struct Solution {
  Long t = 0, c = 0;
  vector<pair<int, int>> edges;
  P getP() const { return P(t, c); }
  Long 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;
  }
};

int n;
vector<tuple<int, Long, Long>> adj[N];

Solution mst(Long coeff_x, Long coeff_y) {
  static const Long OO = LLONG_MAX / 2;
  static const Long VIS = OO - 1;
  static vector<Long> dist(N), best_t(N), best_c(N), best_parent(N);

  fill(all(dist), OO);
  dist[0] = 0;
  Solution sol;
  for (int i = 0; i < n; ++i) {
    int mn = min_element(all(dist)) - begin(dist);
    for (auto [v, t, c] : adj[mn]) {
      if (dist[v] == VIS) continue;
      Long tmp = t * coeff_x + c * coeff_y;
      if (tmp < dist[v]) {
        dist[v] = tmp;
        best_t[v] = t;
        best_c[v] = c;
        best_parent[v] = mn;
      }
    }
    dist[mn] = VIS;
    if (i != 0) {
      sol.t += best_t[mn];
      sol.c += best_c[mn];
      sol.edges.emplace_back(mn, best_parent[mn]);
    }
  }
  return sol;
}
Solution best;
void solve(const P& left_v, const P& right_v, const Solution& left_sol,
           const Solution& right_sol) {
  P mid = (left_sol.getP() - right_sol.getP())
              .rotateCCW90();  // Vector perpendicular to the segment connecting
                               // the left and right points.

  auto sol = mst(mid.x, mid.y);
  best = min(best, sol);
  if (areCollinear(left_sol.getP(), sol.getP(), right_sol.getP())) return;
  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 m;
  cin >> n >> m;

  while (m--) {
    int u, v, t, c;
    cin >> u >> v >> t >> c;
    adj[u].emplace_back(v, t, c);
    adj[v].emplace_back(u, t, c);
  }

  P left_v(0, 1);
  P right_v(1, 0);
  auto left_sol = mst(left_v.x, left_v.y);
  auto right_sol = mst(right_v.x, right_v.y);
  best = min(left_sol, right_sol);
  if (!(left_sol == right_sol)) solve(left_v, right_v, left_sol, right_sol);
  cout << best.t << " " << best.c << endl;
  for (auto [u, v] : best.edges) {
    cout << u << " " << v << endl;
  }

  return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'Solution mst(Long, Long)':
timeismoney.cpp:137:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  137 |     for (auto [v, t, c] : adj[mn]) {
      |               ^
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:195:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  195 |   for (auto [u, v] : best.edges) {
      |             ^

• Subtask 1: 100 / 100