Submission #1231688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231688		saddd	timeismoney (balkan11_timeismoney)	C++20	100 / 100	832 ms	1612 KiB

timeismoney

#include<bits/stdc++.h>
#include <cmath>
#include<fstream>
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const int mxn = 100000, sq = 400;
const ll inf = 1e13, mod = 998244353, pr = 37;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
#define ull unsigned long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF = numeric_limits<ll>::max() / 4;
#define vi vector<int>
struct E{
    ll u, v, w, id;
    bool operator <(const E &other){
        return(w < other.w);
    }
};
int n, m;
ll eu[mxn + 1], ev[mxn + 1], et[mxn + 1], ec[mxn + 1];
int pa[mxn + 1];
struct P{
    ll t, c;
    P(){
        t = c = 0;
    }
};
vector<P>candidates;
vt<int>ansedge;
ll ans = inf;
P anspoint;
int fp(int u){
    if(pa[u] < 0)return(u);
    return(pa[u] = fp(pa[u]));
}
bool unon(int u, int v){
    u = fp(u); v = fp(v);
    if(u == v)return(0);
    if(-pa[u] < -pa[v])swap(u, v);
    pa[u] += pa[v]; pa[v] = u;
    return(1);
}
P find_mst(ll coef_c, ll coef_t){
    //cout << coef_c << " " << coef_t << " ";
    vt<E>edge;
    for(int i = 0; i < m; i++){
        edge.pb({eu[i], ev[i], et[i] * coef_t + ec[i] * coef_c, i});
    }
    sort(ALL(edge));
    for(int i = 0; i < n; i++)pa[i] = -1;
    P res;
    vt<int>idedge;
    for(auto [u, v, w, i]: edge){
        if(unon(u, v)){
            res.t += et[i]; res.c += ec[i];
            idedge.pb(i);
        }
    }
    //cout << res.t << " " << res.c << "\n";
    if(res.t * res.c < ans){
        ans = res.t * res.c; ansedge = idedge;
        anspoint = res;
    }
    return(res);
}
void dnc(P l, P r){
    P mid = find_mst(l.t - r.t, r.c - l.c);
    if(mid.c == l.c && mid.t == l.t)return;
    if(mid.c == r.c && mid.t == r.t)return;
    dnc(l, mid); dnc(mid, r);
}
void solve(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> eu[i] >> ev[i] >> et[i] >> ec[i];
    }
    P upper_point = find_mst(1, 0), lower_point = find_mst(0, 1);
    dnc(upper_point, lower_point);
    cout << anspoint.t << " " << anspoint.c << "\n";
    for(auto i: ansedge){
        cout << eu[i] << " " << ev[i] << "\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tt; tt = 1;
    while(tt--){
        solve();

    }
    return(0);
}

• Subtask 1: 100 / 100