Submission #631083

#	Time	Username	Problem	Language	Result	Execution time	Memory
631083		rainliofficial	timeismoney (balkan11_timeismoney)	C++17	100 / 100	404 ms	6192 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
#define sz(x) (int)x.size()
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 2e5+5, INF = 1e9;
int n, m;

struct State{
    int to, time, cost, from;
};

vector<State> arr[MAXN], output;
pii edges[MAXN];
pair<ll, ll> curMin = {60000, 60000};

void prims(int a, int b){
    auto cmp = [&](State& x, State& y){
        return x.time * a + x.cost * b > y.time * a + y.cost * b;
    };
    priority_queue<State, vector<State>, decltype(cmp)> pq(cmp);
    vector<int> cost(n, INF);
    vector<bool> used(n);
    vector<State> mst; 
    cost[0] = 0;
    pq.push({0, 0, 0, -1});
    while (!pq.empty()){
        State cur = pq.top();
        pq.pop();
        if (used[cur.to]){
            continue;
        }
        used[cur.to] = true;
        mst.push_back(cur);
        for (State x : arr[cur.to]){
            if (x.time * a + x.cost * b < cost[x.to] && !used[x.to]){
                cost[x.to] = x.time * a + x.cost * b;
                pq.push(x);
            }
        }
    }
    ll time = 0, money = 0;
    for (State x : mst){
        time += x.time;
        money += x.cost;
    }
    if (time * money < curMin.first * curMin.second){
        swap(output, mst);
        curMin = {time, money};
    }
}

signed main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    cin >> n >> m;
    for (int i=0; i<m; i++){
        int a, b, t, c;
        cin >> a >> b >> t >> c;
        edges[i] = {t, c};
        arr[a].push_back({b, t, c, a});
        arr[b].push_back({a, t, c, b});
    }
    for (int i=1; i<2000; i++){
        prims(uid(1, 51000), uid(1, 51000));
    }
    cout << curMin.first << " " << curMin.second << "\n";
    for (int i=1; i<sz(output); i++){
        cout << output[i].from << " " << output[i].to << "\n";
    }
}

/**
 * Debugging checklist:
 * - Reset everything after each TC
 * - Integer overflow, index overflow
 * - Special cases?
 */

• Subtask 1: 100 / 100