답안 #786401

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
786401 2023-07-18T07:24:35 Z vjudge1 시간이 돈 (balkan11_timeismoney) C++17
100 / 100
362 ms 1176 KB
/*************************************
*    author: marvinthang             *
*    created: 18.07.2023 14:10:28    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

struct Point {
    long long x, y;
    Point(long long x = 0, long long y = 0): x(x), y(y) {}
    friend scan_op(Point) { return in >> u.x >> u.y; }
    friend print_op(Point) { return out << make_pair(u.x, u.y); }
    bool operator < (const Point &other) const { return make_pair(x, y) < make_pair(other.x, other.y); }
    Point & operator += (const Point &other) {x += other.x; y += other.y; return *this; }
    Point & operator -= (const Point &other) { x -= other.x; y -= other.y; return *this; }
    Point operator + (const Point &other) const { return Point(*this) += other; }
    Point operator - (const Point &other) const { return Point(*this) -= other; }
    
    long long dot(const Point &other) const { return x * other.x + y * other.y; }
    long long cross(const Point &other) const { return x * other.y - y * other.x; }
    long long norm(void) const { return x * x + y * y; }
    long long cross(const Point &a, const Point &b) const { return (a - *this).cross(b - *this); }
};

int sgn(long long val) { return val < 0 ? -1 : !!val; }

int ccw(const Point &a, const Point &b, const Point &c) { return sgn(a.cross(b, c)); }

struct Edge {
	int u, v, t, c;
};

struct DisjointSet {
    
    int n, *lab = nullptr;

    DisjointSet(int _n = 0) {
        resize(_n);
    }

    void reset(void) {
        memset(lab, -1, (n + 1) * sizeof(int));
    }

    void resize(int _n) {
         if (lab != nullptr) delete[] lab;
         n = _n;
         lab = new int[n + 1];
         reset();
    }

    int find(int u) {
        assert(u <= n);
        return lab[u] < 0 ? u : lab[u] = find(lab[u]);
    }

    bool connected(int u, int v) { return find(u) == find(v); }
    bool isRoot(int u) { return lab[u] < 0; }
    int size(int u) { return -lab[find(u)]; }

    bool join(int u, int v) {
        if ((u = find(u)) == (v = find(v))) return false;
        if (lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }

};

using DSU = DisjointSet;

// end of template

const int MAX = 1e4 + 4;

int N, M;
Edge edges[MAX];

void init(void) {
	cin >> N >> M;
	REP(i, M) cin >> edges[i].u >> edges[i].v >> edges[i].t >> edges[i].c;
}

Point res(1e9, 1e9);
int pa, pb;

Point solve_mst(int a, int b, bool trace = false) {
	sort(edges, edges + M, [&] (Edge x, Edge y) { return x.t * a + x.c * b < y.t * a + y.c * b; });
	DSU dsu(N);
	Point p;
	REP(i, M) if (dsu.join(edges[i].u, edges[i].v)) {
		if (trace) cout << edges[i].u << ' ' << edges[i].v << '\n';
		p += Point(edges[i].t, edges[i].c);
	}
	if (res.x * res.y > p.x * p.y) {
		res = p;
		pa = a;
		pb = b;
	}
	return p;
}

void solve(Point l, Point r) {
	if (l.x == r.x || l.y == r.y) return;
	Point m = solve_mst(l.y - r.y, r.x - l.x);
	if (!ccw(l, m, r)) return;
	solve(l, m);
	solve(m, r);
}

void process(void) {
	solve(solve_mst(1, 0), solve_mst(0, 1));
	cout << res.x << ' ' << res.y << '\n';
	solve_mst(pa, pb, true);
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("D");
	init();
	process();
	cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:155:2: note: in expansion of macro 'file'
  155 |  file("D");
      |  ^~~~
timeismoney.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:155:2: note: in expansion of macro 'file'
  155 |  file("D");
      |  ^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 3 ms 404 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 41 ms 840 KB Output is correct
17 Correct 41 ms 792 KB Output is correct
18 Correct 40 ms 820 KB Output is correct
19 Correct 343 ms 1176 KB Output is correct
20 Correct 362 ms 1112 KB Output is correct