Submission #941923

#	Time	Username	Problem	Language	Result	Execution time	Memory
941923		Muaath_5	timeismoney (balkan11_timeismoney)	C++17	100 / 100	364 ms	740 KiB

timeismoney

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

const int N = 1e4+1;
int n, m;

#define ld long double
#define ptype ll
struct vec {
public:
    ptype x, y;
    ld length() const {
        return sqrt(x * x + y * y);
    }
    ptype lengthsq() const {
        return x * x + y * y;
    }
    vec() {}
    vec(ptype x, ptype y) : x(x), y(y) {}
    vec& operator+=(const vec& T) {
        x += T.x;
        y += T.y;
        return *this;
    }
    vec& operator-=(const vec& T) {
        x -= T.x;
        y -= T.y;
        return *this;
    }
    vec& operator*=(const ptype& T) {
        x *= T;
        y *= T;
        return *this;
    }
    vec operator+(const vec& T) const {
        return vec(*this) += T;
    }
    vec operator-(const vec& T) const {
        return vec(*this) -= T;
    }
    vec operator*(const ptype& T) const {
        return vec(*this) *= T;
    }
    // cross product
    friend ll operator^(const vec& a, const vec& buld) {
        return (a.x * buld.y) - (a.y * buld.x);
    }
    // dot product
    friend ll operator&(const vec& a, const vec& buld) {
        return (a.x * buld.x) + (a.y * buld.y);
    }

    
    friend bool operator==(const vec &a, const vec &b) {
        return a.x == b.x && a.y == b.y;
    }

    // unit vector
    friend vec operator~(vec a) {
        const ll jcd = gcd(a.x, a.y);
        a.x /= jcd;
        a.y /= jcd;
        return a;
    }

    // inverse sides
    friend vec operator!(vec a) {
        a.x *= -1;
        a.y *= -1;
        return a;
    }

};
vec norm(const vec& a) {
    return vec(a.y, -a.x);
}

struct edge {
    int x, y, t, c;
} e[N];

int par[N], cnt[N];
int root(int x) {
    return par[x] == x ? x : par[x] = root(par[x]);
}

bool merge(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) return false;
    if (cnt[v] > cnt[u]) swap(u, v);
    par[v] = u;
    cnt[u] += cnt[v];
    return true;
}

void init() {
    for (int i = 0; i < n; par[i] = i, cnt[i] = 1, i++);
}

vec mst(int time_factor, int money_factor)
{
    init();
    sort(e, e + m, [&](edge x, edge y) {
        return time_factor * x.t + money_factor * x.c <
            time_factor * y.t + money_factor * y.c;
        });
    ll curtime = 0, curmoney = 0;
    for (auto ed : e) {
        if (merge(ed.x, ed.y)) {
            curtime += ed.t;
            curmoney += ed.c;
        }
    }
    return vec(curtime, curmoney); // dammam
}

ll sol = 1e18;
vec best = vec(0,0);
void rec(vec a, vec b)
{
    vec dir = norm(b-a); // NOT dammam
    dir = vec(a.y-b.y, b.x-a.x);
    vec res = mst(dir.x, dir.y); // dammam
    if (sol > res.x * res.y) {
        sol = res.x * res.y;
        best = dir;
    }
    if ((a.x*(b.y-res.y)+b.x*(res.y-a.y)+res.x*(a.y-b.y)) != 0) {
        rec(a, res);
        rec(res, b);
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> e[i].x >> e[i].y >> e[i].t >> e[i].c;

    vec mst_t = mst(1, 0),
        mst_m = mst(0, 1);

    best = vec(1, 0);
    sol = mst_t.x * mst_t.y;

    if (sol > mst_m.x * mst_m.y) {
        sol = mst_m.x * mst_m.y;
        best = vec(0, 1);
    }
    // NOT dammam ofc
    rec(mst_t, mst_m);

    
    best = mst(best.x, best.y);
    init();
    
    cout << best.x << ' ' << best.y << '\n';
    for (auto ed : e) {
        if (merge(ed.x, ed.y)) {
            cout << ed.x << ' ' << ed.y << '\n';
        }
    }
}

• Subtask 1: 100 / 100