Submission #1141813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141813		qqusayy	시간이 돈 (balkan11_timeismoney)	C++20	5 / 100	4 ms	1816 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, c, t, 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;
    }
    
};



int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

    ll n, m;
    cin >> n >> m;
    DSU t, t1, t2;
    vector<pair<ll, ll>> ans, ans1, ans2;
    vector<edge> edges, edges1, edges2;
    for (int i = 0; i < m; i++) {
        ll x, y, C, T;
        cin >> x >> y >> T >> C;
        edges.PB({x, y,T, C, T});
        edges1.PB({x, y,T, C, C});
        edges2.PB({x, y,T, C, C + T});
        t.create(x);
        t.create(y);
        t1.create(x);
        t1.create(y);
        t2.create(x);
        t2.create(y);
    }
    sort(edges.B, edges.E);
    ll c = 0, tim = 0, v = 0, v1 = 0, v2 = 0, c1 = 0, tim1 = 0, c2 = 0, tim2 = 0;
    for (edge e : edges) {
        if (t.unite(e.a, e.b)) {
            ans.PB({e.a, e.b});
            c += e.c;
            tim += e.t;
        }
    } v = tim * c;
    for (edge e : edges1) {
        if (t1.unite(e.a, e.b)) {
            ans1.PB({e.a, e.b});
            c1 += e.c;
            tim1 += e.t;
        }
    } v1 = c1 * tim1;
    
    for (edge e : edges2) {
        if (t2.unite(e.a, e.b)) {
            ans2.PB({e.a, e.b});
            c2 += e.c;
            tim2 += e.t;
        }
    } v2 = c2 * tim2;
    if (v >= v2 && v >= v1) {
        cout << tim << P << c << L;
        for (auto [u, v] : ans) cout << u << P << v << L;
    }
    else if (v1 >= v2 && v1 >= v) {
        cout << tim1 << P << c1 << L;
        for (auto [u, v] : ans1) cout << u << P << v << L;
    }
    else if (v2 >= v1 && v2 >= v) {
        cout << tim2 << P << c2 << L;
        for (auto [u, v] : ans2) cout << u << P << v << L;
    }
}

• Subtask 1: 5 / 100