oj.uz

Submission #491721

# Submission time Handle Problem Language Result Execution time Memory
491721 2021-12-04T03:10:44 Z clams timeismoney (balkan11_timeismoney) C++17
100 / 100
 82 ms 924 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;

const int mxn = 205;
const int mxm = 10005;
const db MAX = 1e5;

struct Edge {
    ll a, b, t, c;
    db k;
    
    bool operator < (const Edge& oth) const {
        return k < oth.k;
    }    
};

int n, m, par[mxn], sz[mxn];
vector<Edge> v;

int fd(int u) {
    return par[u] = (par[u] == u ? u : fd(par[u]));    
}

bool unn(int u, int v) {
    u = fd(u);
    v = fd(v);
    if(u == v) return false;
    if(sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    par[v] = u;
    return true;
}

void init(ll x) {
    iota(par, par + n, 0);
    fill(sz, sz + n, 1);
    for(auto& [a, b, t, c, k] : v)
        k = c * x + t * (MAX - x);
    sort(v.begin(), v.end());
}

ll solve(db mid) {
    init(mid);
    int solt = 0, solc = 0;
    for(auto [a, b, t, c, k] : v) {
        if(unn(a, b)) {
            solt += t;
            solc += c;
        }
    }
    return 1LL * solt * solc;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> m;
    v.resize(m);
    for(auto& [a, b, t, c, w] : v) cin >> a >> b >> t >> c;
        
    db l = 0, r = MAX;
    for(int ite = 0; ite < 70; ite++) {
        db m1 = (2 * l + r) / 3;
        db m2 = (l + 2 * r) / 3;
        if(solve(m1) < solve(m2)) r = m2;
        else l = m1;
    }
    
    init(l);
    vector<pair<int, int>> ans;
    int sumt = 0, sumc = 0;
    for(auto [A, B, t, c, k] : v) {
        if(unn(A, B)) {
            sumt += t;
            sumc += c;
            ans.push_back({A, B});
        }
    }
    
    cout << sumt << ' ' << sumc << '\n';
    for(auto [a, b] : ans) cout << a << ' ' << b << '\n';
}

// from: https://oj.uz/submission/482787

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 2 ms 324 KB Output is correct
7 Correct 13 ms 440 KB Output is correct
8 Correct 65 ms 920 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 14 ms 432 KB Output is correct
17 Correct 13 ms 432 KB Output is correct
18 Correct 14 ms 332 KB Output is correct
19 Correct 80 ms 924 KB Output is correct
20 Correct 82 ms 920 KB Output is correct