oj.uz

Submission #43268

# Submission time Handle Problem Language Result Execution time Memory
43268 2018-03-12T08:40:12 Z ngkan146 timeismoney (balkan11_timeismoney) C++11
100 / 100
 656 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], 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 660 KB Output is correct
7 Correct 3 ms 660 KB Output is correct
8 Correct 8 ms 956 KB Output is correct
9 Correct 2 ms 956 KB Output is correct
10 Correct 2 ms 956 KB Output is correct
11 Correct 2 ms 956 KB Output is correct
12 Correct 2 ms 956 KB Output is correct
13 Correct 2 ms 956 KB Output is correct
14 Correct 9 ms 956 KB Output is correct
15 Correct 5 ms 956 KB Output is correct
16 Correct 72 ms 956 KB Output is correct
17 Correct 75 ms 956 KB Output is correct
18 Correct 79 ms 956 KB Output is correct
19 Correct 656 ms 1004 KB Output is correct
20 Correct 627 ms 1004 KB Output is correct