oj.uz

Submission #684628

# Submission time Handle Problem Language Result Execution time Memory
684628 2023-01-22T07:29:07 Z vjudge1 timeismoney (balkan11_timeismoney) C++17
100 / 100
 745 ms 1000 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 5 ms 988 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 3 ms 336 KB Output is correct
16 Correct 82 ms 596 KB Output is correct
17 Correct 83 ms 476 KB Output is correct
18 Correct 79 ms 468 KB Output is correct
19 Correct 733 ms 1000 KB Output is correct
20 Correct 745 ms 996 KB Output is correct