oj.uz

Submission #43265

# Submission time Handle Problem Language Result Execution time Memory
43265 2018-03-12T08:36:40 Z ngkan146 timeismoney (balkan11_timeismoney) C++11
100 / 100
 666 ms 1752 KB 
#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];
int dsu_p(int x){
    return dsup[x] == x ? x : dsup[x] = dsu_p(dsup[x]);
}
void dsu_union(int x,int y){
    dsup[dsu_p(y)] = dsu_p(x);
}
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;
    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 = res;
        lstt = 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 1 ms 568 KB Output is correct
5 Correct 2 ms 576 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 3 ms 752 KB Output is correct
8 Correct 7 ms 1268 KB Output is correct
9 Correct 1 ms 1268 KB Output is correct
10 Correct 1 ms 1268 KB Output is correct
11 Correct 1 ms 1268 KB Output is correct
12 Correct 2 ms 1268 KB Output is correct
13 Correct 2 ms 1268 KB Output is correct
14 Correct 7 ms 1268 KB Output is correct
15 Correct 5 ms 1268 KB Output is correct
16 Correct 74 ms 1268 KB Output is correct
17 Correct 82 ms 1268 KB Output is correct
18 Correct 74 ms 1268 KB Output is correct
19 Correct 626 ms 1612 KB Output is correct
20 Correct 666 ms 1752 KB Output is correct