oj.uz

Submission #43266

# Submission time Handle Problem Language Result Execution time Memory
43266 2018-03-12T08:38:21 Z ngkan146 timeismoney (balkan11_timeismoney) C++11
100 / 100
 649 ms 1004 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 = 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 1 ms 480 KB Output is correct
3 Correct 1 ms 480 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 2 ms 540 KB Output is correct
6 Correct 2 ms 556 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 7 ms 984 KB Output is correct
9 Correct 2 ms 984 KB Output is correct
10 Correct 1 ms 984 KB Output is correct
11 Correct 2 ms 984 KB Output is correct
12 Correct 2 ms 984 KB Output is correct
13 Correct 2 ms 984 KB Output is correct
14 Correct 7 ms 984 KB Output is correct
15 Correct 5 ms 984 KB Output is correct
16 Correct 77 ms 984 KB Output is correct
17 Correct 81 ms 984 KB Output is correct
18 Correct 76 ms 984 KB Output is correct
19 Correct 631 ms 1004 KB Output is correct
20 Correct 649 ms 1004 KB Output is correct