답안 #300080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
300080	2020-09-16T13:20:26 Z	Mohammad_Yasser	시간이 돈 (balkan11_timeismoney)	C++14	90 / 100	2000 ms	640 KB

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

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-9) 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;
}

Subtask #1
90.0 / 100.0

#	결과	실행 시간	메모리	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	1 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	7 ms	640 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	3 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	54 ms	384 KB	Output is correct
15	Correct	39 ms	504 KB	Output is correct
16	Correct	870 ms	504 KB	Output is correct
17	Correct	924 ms	504 KB	Output is correct
18	Correct	870 ms	504 KB	Output is correct
19	Execution timed out	2083 ms	640 KB	Time limit exceeded
20	Execution timed out	2080 ms	640 KB	Time limit exceeded

답안 #300080

Compilation message

Subtask #1 90.0 / 100.0

Subtask #1
90.0 / 100.0