Submission #1266681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266681		huyjavalt	timeismoney (balkan11_timeismoney)	C++20	0 / 100	2096 ms	131072 KiB

timeismoney

#include <bits/stdc++.h>

using namespace std;

#define double long double
#define int long long

int t[100005];
int c[100005];
pair<int,int> e[100005];
vector<pair<int,int>> p;
int par[100005];

int find_set(int v){
    if(v == par[v]) return v;
    return par[v] = find_set(par[v]);
}

void union_set(int u, int v){
    u = find_set(u), v = find_set(v);
    if(u != v) par[v] = u;
}

int n,m;

pair<pair<int,int>, vector<int>> MST(){
    for(int i = 1; i <= n; i++) par[i] = i;
    pair<int,int> ans;
    vector<int> res;

    for(int i = 1; i <= m; i++){
        int id = p[i-1].second;
        if(find_set(e[id].first) != find_set(e[id].second)){
            ans.first += t[id];
            ans.second += c[id];
            res.push_back(id);
            union_set(e[id].first,e[id].second);
        }
    }

    return {ans,res};
}

int area(pair<int,int> A, pair<int,int> B, pair<int,int> P) {
	pair<int,int> AB = {B.first - A.first, B.second - A.second};
	pair<int,int> AP = {P.first - A.first, P.second - A.second};
	return AB.first * AP.second - AB.second * AP.first;
}


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("mbp.inp","r",stdin);
//    freopen("mbp.out","w",stdout);
    cin >> n >> m;

    for(int i = 1; i <= m; i++){
        int u,v;
        cin >> u >> v;
        u++, v++;
        e[i] = {u,v};
        cin >> t[i] >> c[i];
    }

    pair<int,int> best = {1e9,1e9};
    vector<int> tree;

    for(int i = 1; i <= m; i++) p.push_back({t[i],i});
    sort(p.begin(), p.end());
    auto [A,cur] = MST();
    if(best.first * best.second > A.first * A.second){
        best = A;
        tree = cur;
    }
    p.clear();

    for(int i = 1; i <= m; i++) p.push_back({c[i],i});
    sort(p.begin(), p.end());
    auto [B,cur2] = MST();
    if(best.first * best.second > B.first * B.second){
        best = B;
        tree = cur2;
    }
    p.clear();

    queue< pair<pair<int,int>,pair<int,int>> > q;
    q.push({A,B});

    while(q.size()){
        auto [A,B] = q.front(); q.pop();

        for(int i = 1; i <= m; i++) p.push_back({c[i] * (B.first - A.first) - t[i] * (B.second - A.second),i});
        sort(p.begin(), p.end());

        auto [C,cur3] = MST();
        if(best.first * best.second > B.first * B.second){
            best = C;
            tree = cur3;
        }
        p.clear();

        if(area(A,B,C) > 0) continue;

        q.push({A,C});
        q.push({C,B});
    }

    cout << best.first << ' ' << best.second << '\n';
    for(auto i : tree) cout << e[i].first-1 << ' ' << e[i].second-1 << '\n';


    return 0;
}

• Subtask 1: 0 / 100