제출 #237674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237674		VEGAnn	시간이 돈 (balkan11_timeismoney)	C++14	100 / 100	1338 ms	760 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){
    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;

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

    gcnt++;

//    cerr << fixed << setprecision(10) << ga << " " << gb << '\n';
//    for (int i = 0; i < m; i++)
//        cerr << nm[i] << '\n';
//    cerr << '\n';

    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){
//    cerr << lf[0] << " " << lf[1] << '\n' << rt[0] << " " << rt[1] << '\n';

    ld na = ld(rt[1]) - ld(lf[1]);
    ld nb = ld(lf[0]) - ld(rt[0]);

    if (na < 0){
        na = -na;
        nb = -nb;
    }

    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: 100 / 100