Submission #684628

#	Time	Username	Problem	Language	Result	Execution time	Memory
684628		vjudge1	timeismoney (balkan11_timeismoney)	C++17	100 / 100	745 ms	1000 KiB

timeismoney

#define taskname "timeismoney"
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define ff first
#define ss second

using namespace std;
const int maxn = 1e4 + 10;
int n, m, x[maxn], y[maxn], t[maxn], c[maxn], id[maxn], p[maxn], w[maxn], mark[maxn];
iii anss;

inline int fp(int u) {return !p[u] ? u : p[u] = fp(p[u]);}
inline bool uni(int u, int v)
{
    if ((u = fp(u)) == (v = fp(v))) return 0;
    return p[v] = u, 1;
}

inline ii mst(int T, int C)
{
    int g = __gcd(T, C);
    T /= g, C /= g;
    for (int i=1; i<=m; i++) w[i] = T * t[i] + C * c[i], id[i] = i, mark[i] = 0;
    fill(p+1, p+n+1, 0);
    sort(id+1, id+m+1, [](int x, int y){return w[x] < w[y];});
    ii ans = {0, 0};
    for (int i=1; i<=m; i++)
    {
        int _id = id[i];
        if (uni(x[_id], y[_id])) ans.ff += t[_id], ans.ss += c[_id], mark[_id] = 1;
    }
    return ans;
}

void solve(ii x, ii y)
{
    if (x == y) return;
    ii mid = mst(x.ss - y.ss, y.ff - x.ff);
    anss = min(anss, {mid.ff * mid.ss, {x.ss-y.ss, y.ff-x.ff}});
    if (mid == x || mid == y) return;
    solve(x, mid);
    solve(mid, y);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>x[i]>>y[i]>>t[i]>>c[i], x[i]++, y[i]++;
    ii xx = mst(0, 1), yy = mst(1, 0);
    anss = {xx.ff * xx.ss, {0, 1}};
    anss = min(anss, {yy.ff * yy.ss, {1, 0}});
    solve(xx, yy);
    ii tmp = mst(anss.ss.ff, anss.ss.ss);
    cout<<tmp.ff<<" "<<tmp.ss<<"\n";
    for (int i=1; i<=m; i++) if (mark[i]) cout<<x[i]-1<<" "<<y[i]-1<<"\n";
}

/**
5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92
**/

• Subtask 1: 100 / 100