Submission #1244193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244193		yue_lai	timeismoney (balkan11_timeismoney)	C++20	45 / 100	6 ms	1156 KiB

timeismoney

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    long long int u, v;
    long long int cost;
    long long int t, c;
};

bool cmp(const Edge& a, const Edge& b) {
    return a.cost < b.cost;
}

vector<long long int> p; // 改為全域 vector

long long int find_set(long long int i) {
    if (p[i] == i)
        return i;
    return p[i] = find_set(p[i]); // Path Compression
}

void unite_sets(long long int i, long long int j) {
    long long int root_i = find_set(i);
    long long int root_j = find_set(j);
    if (root_i != root_j) {
        p[root_j] = root_i;
    }
}

int main() {
    long long int n, m;
    while (cin >> n >> m) {
        p.assign(n, 0); // 調整 p 的大小並初始化
        for (long long int i = 0; i < n; i++) {
            p[i] = i;
        }

        vector<Edge> edges;
        for (long long int i = 0; i < m; i++) {
            long long int u, v, t, c;
            cin >> u >> v >> t >> c;
            edges.push_back({u, v, t * c, t, c});
        }

        sort(edges.begin(), edges.end(), cmp);

        long long int ans1 = 0;
        long long int ans2 = 0;
        vector<pair<long long int, long long int>> mst_edges;
        int edges_count = 0;

        for (const auto& edge : edges) {
            if (find_set(edge.u) != find_set(edge.v)) {
                unite_sets(edge.u, edge.v);
                ans1 += edge.t;
                ans2 += edge.c;
                mst_edges.push_back({edge.u, edge.v});
                edges_count++;
            }
        }

        if (edges_count == n - 1) {
            cout << ans1 << " " << ans2 << "\n";
            for (const auto& edge : mst_edges) {
                cout << edge.first << " " << edge.second << endl;
            }
        } else {
            cout << "-1\n";
        }
    }
    return 0;
}

• Subtask 1: 45 / 100