Submission #1010558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010558		vjudge1	timeismoney (balkan11_timeismoney)	C++17	90 / 100	2083 ms	2716 KiB

timeismoney

// ^^
// <{:3
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define int long signed long int
#define ld long double
using namespace std;
const int maxn = 202;
vector<tuple<ld, ld, int, int>> edges; // c t x y
pair<int, ld> ans; // val, k
int p[maxn];
int n, m;

inline void rt() { for(int i = 0; i <= n; ++i) p[i] = i; }

int f(int x)
{
    if(p[x] == x) return x;
    return p[x] = f(p[x]);
}

inline void u(int x, int y)
{
    x = f(x); y = f(y);
    if(x == y) return;
    p[x] = y;
}

pair<int, int> mst(ld k)
{
    vector<tuple<ld, ld, ld, int, int>> v;
    rt();

    for(auto [c, t, x, y] : edges) v.emplace_back(t+k*c, c, t, x, y);
    sort(v.begin(), v.end());

    pair<int, int> ret(0, 0);
    for(auto [val, c, t, x, y] : v)
    {
        if(f(x) != f(y))
        {
            ret.first += c;
            ret.second += t;
            u(x, y);
        }
    }

    return ret;
}

void rec(ld x1, ld y1, ld x2, ld y2, int dep)
{
    if(x1 == x2) return;

    //cout << x1 << " " << y1 << " " << x2 << " " << y2 << " bananus" << endl;
    if(dep > 10) return;

    ld k = (y1 - y2) / (x1 - x2);
    ld c = y1 - (k * x1);

    pair<int, int> novi = mst(-k);

    ld y = (k*novi.first) + c;

    //cout << novi.first << " " << novi.second << " " << k << " dbdb\n";

    if(novi.second >= y) return;

    if(novi.first * novi.second < ans.first)
    {
        ans.first = novi.first * novi.second;
        ans.second = k;
    }

    rec(x1, y1, novi.first, novi.second, dep+1);
    rec(x2, y2, novi.first, novi.second, dep+1);
}

signed main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    //freopen("10-timeismoney.in", "r", stdin);
    ans = {1e9, 0};

    cin >> n >> m;

    for(int i = 0; i < m; ++i)
    {
        ld t, c;
        int x, y;
        cin >> x >> y >> t >> c;
        edges.emplace_back(t, c, x, y);
    }

    rt();
    vector<pair<int, int>> minte, mince;
    sort(edges.begin(), edges.end());
    pair<int, int> mint(0, 0);
    for(auto &[t, c, x, y] : edges)
    {
        int xtr = f(x), ytr = f(y);
        if(xtr != ytr)
        {
            mint.first += c;
            mint.second += t;
            minte.emplace_back(x, y);
            u(xtr, ytr);
        }
        swap(t, c);
    }

    rt();
    sort(edges.begin(), edges.end());
    pair<int, int> minc(0, 0);
    for(auto &[c, t, x, y] : edges)
    {
        int xtr = f(x), ytr = f(y);
        if(xtr != ytr)
        {
            minc.first += c;
            minc.second += t;
            mince.emplace_back(x, y);
            u(xtr, ytr);
        }
    }

    rec(minc.first, minc.second, mint.first, mint.second, 0);

    if(minc.first * minc.second < ans.first)
    {
        swap(minc.first, minc.second);
        cout << minc.first << " " << minc.second << "\n";
        for(auto [x, y] : mince) cout << x << " " << y << "\n";
        return 0;
    }
    if(mint.first * mint.second < ans.first)
    {
        swap(mint.first, mint.second);
        cout << mint.first << " " << mint.second << "\n";
        for(auto [x, y] : minte) cout << x << " " << y << "\n";
        return 0;
    }


    rt();
    ld k = -ans.second;
    vector<tuple<ld, ld, ld, int, int>> v;
    for(auto [c, t, x, y] : edges) v.emplace_back(t+k*c, c, t, x, y);

    sort(v.begin(), v.end());

    pair<int, int> ret(0, 0);
    vector<pair<int, int>> ansedge;
    for(auto [val, c, t, x, y] : v)
    {
        if(f(x) != f(y))
        {
            ret.first += c;
            ret.second += t;
            u(x, y);
            ansedge.emplace_back(x, y);
        }
    }

    swap(ret.first, ret.second);
    cout << ret.first << " " << ret.second << "\n";
    for(auto [x, y] : ansedge) cout << x << " " << y << "\n";
}

• Subtask 1: 90 / 100