Submission #43268

#	Time	Username	Problem	Language	Result	Execution time	Memory
43268		ngkan146	timeismoney (balkan11_timeismoney)	C++11	100 / 100	656 ms	1004 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
struct edge{
    int u,v,w1,w2;
    edge(int u=0,int v=0,int w1=0,int w2=0): u(u), v(v), w1(w1), w2(w2) {}
};
int dsup[205], dsusize[205];
int dsu_p(int x){
    return dsup[x] == x ? x : dsup[x] = dsu_p(dsup[x]);
}
void dsu_union(int x,int y){
    x = dsu_p(x);
    y = dsu_p(y);
    if (dsusize[x] > dsusize[y])    swap(x, y);
    dsusize[y] += dsusize[x];
    dsup[x] = y;
}
int n, m;
vector <edge> lst;
typedef pair<int,int> mst;
mst ans;
int answer;
vector <mst> lstt;
mst find_mst(int v1,int v2){
    sort(lst.begin(), lst.end(), [&](edge x,edge y){
         return x.w1 * v1 + x.w2 * v2 != y.w1 * v1 + y.w2 * v2 ? x.w1 * v1 + x.w2 * v2 < y.w1 * v1 + y.w2 * v2 : x.w1 < y.w1;
    });
    for(int i=1;i<=n;i++)
        dsup[i] = i,
        dsusize[i] = 1;
    mst res;
    vector <mst> mjk;
    for(auto e: lst){
        if (dsu_p(e.u) != dsu_p(e.v))
            dsu_union(e.u, e.v),
            mjk.push_back({e.u, e.v}),
            res.first += e.w1,
            res.second += e.w2;
    }
    if (answer > res.first * res.second){
        answer = res.first * res.second;
        ans = move(res);
        lstt = move(mjk);
    }
    return res;
}
void solve(mst a,mst b){
    mst tmp = find_mst(a.second - b.second, - a.first + b.first);
    if (a.first != tmp.first && a.second != tmp.second &&
        b.first != tmp.first && b.second != tmp.second)
            solve(a, tmp), solve(tmp, b);
}
int main(){
    answer = (int) 2e9;
    iostream::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int u,v,w1,w2;
        cin >> u >> v >> w1 >> w2;
        u ++; v ++;
        lst.push_back(edge(u, v, w1, w2));
    }
    solve(find_mst(1,0), find_mst(0, 1));
    cout << ans.first << ' ' << ans.second << endl;
    for(auto v: lstt)
        cout << v.first-1 << ' ' << v.second-1 << endl;
}

• Subtask 1: 100 / 100