Submission #1166200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166200		12345678	timeismoney (balkan11_timeismoney)	C++20	50 / 100	175 ms	972 KiB

timeismoney

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e2+5, mx=1e4+5;

ll n, m, dsu[nx], u[mx], v[mx], t[mx], c[mx], res=1e18, rest, resc;
vector<pair<ll, ll>> ans;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>u[i]>>v[i]>>t[i]>>c[i];
    for (int x=1; x<=15; x++)
    {
        for (int y=1; y<=15; y++)
        {
            for (int i=0;i <n;i ++) dsu[i]=i;
            vector<tuple<int, int>> edg;
            ans.clear();
            ll smt=0, smc=0;
            for (int i=1; i<=m; i++) edg.push_back({x*t[i]+y*c[i], i});
            sort(edg.begin(), edg.end());
            for (auto [_, idx]:edg)
            {
                if (find(u[idx])==find(v[idx])) continue;
                ans.push_back({u[idx], v[idx]});
                smt+=t[idx], smc+=c[idx];
                dsu[find(u[idx])]=find(v[idx]);
            }
            if (smt*smc<res)
            {
                res=smt*smc;
                rest=smt;
                resc=smc;
            }
        }
    }
    cout<<rest<<' '<<resc<<'\n';
    for (auto [i, j]:ans) cout<<i<<' '<<j<<'\n';
}

• Subtask 1: 50 / 100