제출 #1142282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142282		qqusayy	시간이 돈 (balkan11_timeismoney)	C++20	35 / 100	571 ms	1624 KiB

timeismoney

#include "bits/stdc++.h"
#define P ' '
#define L '\n'
#define F first
#define S size()
#define PB push_back
#define B begin()
#define E end()
#define SS second
#define PBB pop_back()
using ll = long long;
using namespace std;

struct edge {
    ll a, b, t, c, weight;
    bool operator< (edge x) const {
        return weight < x.weight;
    }
};
struct DSU{
    ll parent[202];
    
    void create(ll x) {
        parent[x] = x;
    }
    ll find(ll x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
    bool unite(ll a, ll b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
            return 1;
        }
        return 0;
    }
    
};
struct check {
    ll v = 1e9, t = 0, c = 0;
    vector<pair<ll, ll>> ans;
    
    bool operator< (check x) const {
        return v < x.v;
    }
};
check best;
vector<edge> edges;

check MST(ll a, ll b) {
    DSU t;
    for (edge e : edges) {
        t.create(e.a);
        t.create(e.b);
    }
    vector<edge> e;
    e = edges;
    for (edge &i : e) i.weight = (i.t * a) + (i.c * b);
    sort(e.B, e.E);
    check out;
    for (edge i : e) {
        if (t.unite(i.a, i.b)) {
            out.c += i.c;
            out.t += i.t;
            out.ans.PB({i.a, i.b});
        }
    }
    out.v = out.c * out.t;
    return out;
}

check solve(ll c1, ll c2, ll t1 ,ll t2) {
    ll a = c1 - c2, b = t2 - t1;
    check mst = MST(a, b);
    if ((mst.c == c2 && mst.t == t2) || (mst.t == t1 && mst.c == c1)) return mst;
    
    return best = min(solve(c1, mst.c, t1, mst.t), solve(mst.c, c2, mst.t, t2));
}


int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    
    ll n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        ll x, y, C, T;
        cin >> x >> y >> T >> C;
        edges.PB({x, y,T, C, 0});
    }
    check btime = MST(1, 0);
    check bcost = MST(0, 1);
    best = min(btime, bcost);
    solve(btime.c, bcost.c, btime.t, bcost.t);
    cout << best.t << P << best.c << L;
    for (auto i : best.ans) cout << i.F << P << i.SS << L;
}

• Subtask 1: 35 / 100