제출 #322626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
322626		denverjin	timeismoney (balkan11_timeismoney)	C++14	100 / 100	511 ms	844 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

struct Edge {
    int u, v, a, b, c;
    Edge(int u, int v, int a, int b, int c):
        u(u), v(v), a(a), b(b), c(c) {}
    bool operator < (const Edge &o) const {
        return c != o.c ? c < o.c : (a != o.a ? a < o.a : b < o.b);
    }
};

struct Point {
    int x, y;
    vector <Edge> T;
    Point(): x(), y(), T() {}
    Point(int x, int y, vector <Edge> &T): x(x), y(y), T(T) {}
    bool operator < (const Point &o) const {
        return x != o.x ? x < o.x : y < o.y;
    }
    bool operator == (const Point &o) const {
        return x == o.x && y == o.y;
    }
    friend ostream &operator << (ostream &o, Point x) {
        return o << "(" << x.x << ", " << x.y << ")";
    }
};

struct UnionFind {
    vector <int> fa;
    UnionFind(int n): fa(n) {
        rep(i, n) fa[i] = i;
    }
    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }
    bool merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return 0;
        fa[x] = y;
        return 1;
    }
};

int n, m;
vector <Edge> E;
pair <int, Point> ans(0x3f3f3f3f, Point());

Point kruskal(int ka, int kb) {
    rep(i, m) E[i].c = E[i].a * ka + E[i].b * kb;
    sort(E.begin(), E.end());
    Point ans;
    UnionFind uf(n);
    rep(i, m) {
        if (uf.merge(E[i].u, E[i].v)) {
            ans.x += E[i].a;
            ans.y += E[i].b;
            ans.T.pb(E[i]);
        }
    }
    return ans;
}

void solve(Point A, Point B) {
    ans = min(ans, mp(A.x * A.y, A));
    ans = min(ans, mp(B.x * B.y, B));
    if (A.x > B.x || A.y < B.y) return ;
    Point C = kruskal(-(B.y - A.y), B.x - A.x);
    if (C == A || C == B) return ;
    solve(A, C); solve(C, B);
}

int main() {
    cin >> n >> m;
    rep(i, m) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        E.pb(Edge(u, v, a, b, 0));
    }
    Point A = kruskal(1, 0);
    Point B = kruskal(0, 1);
    solve(A, B);
    cout << ans.second.x << " " << ans.second.y << endl;
    rep(i, ans.second.T.size())
        cout << ans.second.T[i].u << " " << ans.second.T[i].v << endl;
    return 0;
}

• Subtask 1: 100 / 100