Submission #1240258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240258		pemguimn	timeismoney (balkan11_timeismoney)	C++20	100 / 100	811 ms	1760 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>


const int N = 2e6 + 5, MOD = 1e9 + 7, INF = 1e18;  

int n, m;

struct DSU{
    vector<int> par, sz;
    int n;

    DSU(int _n = 0){
        init(_n);
    }

    void init(int _n){
        n = _n; par.resize(n + 1, 0), sz.resize(n + 1, 0);
        for(int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    }
    int root(int x){
        return par[x] = (x == par[x] ? x : root(par[x]));
    }

    bool unite(int x, int y){
        x = root(x), y = root(y);
        if(x != y){
            if(sz[x] < sz[y]) swap(x, y);
            sz[x] += sz[y], par[y] = x;
            return true;
        }
        return false;
    }
}; 


struct Edge{
    int u, v, t, c;
};

struct st{
    int st = 0, sc = 0;
    vector<int> eid;
};

vector<Edge> e;

st optimal(int a, int b){
    vector<int> id(m); iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int x, int y){
        return e[x].t * a + e[x].c * b < e[y].t * a + e[y].c * b;
    });
    st ans;
    DSU tmp(n);
    ans.eid.reserve(n);
    for(int x : id){
        if(tmp.unite(e[x].u, e[x].v)){
            ans.eid.push_back(x);
            ans.st += e[x].t, ans.sc += e[x].c;
        }
    }
    return ans;
}

vector<st> v;

void dnc(st l, st r){
    int na = r.st - l.st, nb = r.sc - l.sc;
    st nw = optimal(-nb, na);
    if(nw.st == l.st && nw.sc == l.sc) return;
    if(nw.st == r.st && nw.sc == r.sc) return;
    int na1 = nw.st - l.st, nb1 = nw.sc - l.sc;
    if(na1 * nb == nb1 * na) return;
    v.push_back(nw);
    dnc(l, nw), dnc(nw, r);
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v, t, c; cin >> u >> v >> t >> c;
        e.push_back({u, v, t, c});
    }
    st m1 = optimal(1, 0);
    st m2 = optimal(0, 1);
    v.reserve(300);
    v.push_back(m1);
    v.push_back(m2);
    dnc(m1, m2);
    int ans = INF;
    st best;
    for(st cur : v){
        if(ans > cur.st * cur.sc){
            ans = cur.st * cur.sc;
            best = cur;
        }        
    }
    cout << best.st << ' ' << best.sc << '\n';
    for(int id : best.eid){
        cout << e[id].u << ' ' << e[id].v << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int t = 1; 

    while(t--){
        solve();
    }
}

• Subtask 1: 100 / 100