Submission #237622

#	Time	Username	Problem	Language	Result	Execution time	Memory
237622		VEGAnn	timeismoney (balkan11_timeismoney)	C++14	40 / 100	15 ms	512 KiB

timeismoney

#include <bits/stdc++.h>
#define l2 array<ll,2>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 210;
const int M = 10010;
const ll OO = 1e18;
const ld E = 1e-9;
int n, m, x[M], y[M], t[M], c[M], nm[M], pr[N], gcnt = 0, msa, msb;
ll ans = OO;
ld ga, gb, ma, mb;

ld func(int nm){
    return ld(t[nm]) * ga + ld(c[nm]) * gb;
}

bool cmp(int _x, int _y){
    if (abs(func(_x) - func(_y)) < E){
        if (t[_x] == t[_y])
            return c[_x] < c[_y];
        else return t[_x] < t[_y];
    } else return (func(_x) < func(_y));
}

bool cmp1(int _x, int _y){
    if (t[_x] == t[_y])
        return c[_x] < c[_y];
    else return t[_x] < t[_y];
}

bool cmp2(int _x, int _y){
    if (c[_x] == c[_y])
        return t[_x] < t[_y];
    else return c[_x] < c[_y];
}

int get(int x) { return (pr[x] == x ? x : pr[x] = get(pr[x])); }

l2 build(ld a, ld b, bool flag){
    ga = a; gb = b;

    if (gcnt == 0)
        sort(nm, nm + m, cmp1);
    else if (gcnt == 1)
        sort(nm, nm + m, cmp2);
    else sort(nm, nm + m, cmp);

    gcnt++;

    for (int i = 0; i < n; i++)
        pr[i] = i;

    int sa = 0, sb = 0;

    for (int it = 0; it < m; it++){
        int i = nm[it];

        int cx = get(x[i]), cy = get(y[i]);

        if (cx == cy) continue;

        if (flag)
            cout << x[i] << " " << y[i] << '\n';

        pr[cx] = cy;

        sa += t[i];
        sb += c[i];
    }

    if (ans > ll(sa) * ll(sb)){
        ans = ll(sa) * ll(sb);
        msa = sa;
        msb = sb;
        ma = ga;
        mb = gb;
    }

    return {sa, sb};
}

bool ok(l2 fi, l2 se, l2 td){
    return (se[0] - fi[0]) * (td[1] - fi[1]) - (se[1] - fi[1]) * (td[0] - fi[0]) < 0;
}

void calc(l2 lf, l2 rt){
    ld na = ld(rt[1]) - ld(lf[1]);
    ld nb = ld(lf[0]) - ld(rt[0]);

    l2 cur = build(na, nb, 0);

    if (!ok(lf, rt, cur)) return;

    calc(lf, cur);
    calc(cur, rt);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        cin >> x[i] >> y[i] >> t[i] >> c[i];
        nm[i] = i;
    }

    calc(build(1.0, 0.0, 0), build(0.0, 1.0, 0));

    cout << msa << " " << msb << '\n';

    build(ma, mb, 1);

    return 0;
}

• Subtask 1: 40 / 100