Submission #488719

#	Time	Username	Problem	Language	Result	Execution time	Memory
488719		InternetPerson10	timeismoney (balkan11_timeismoney)	C++17	45 / 100	5 ms	592 KiB

timeismoney

#include <vector>
#include <iostream>
#include <algorithm>
typedef long long ll;

using namespace std;

struct dsu {
    vector<int> par, siz;
    void init(int n) {
        par.resize(n);
        siz.resize(n, 1);
        for(int i = 0; i < n; i++) par[i] = i;
    }
    int get(int x) {
        if(par[x] == x) return x;
        return par[x] = get(par[x]);
    }
    bool unite(int x, int y) {
        x = get(x); y = get(y);
        if(x == y) return false;
        if(siz[x] > siz[y]) swap(x, y);
        par[x] = y;
        siz[y] += siz[x];
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    dsu uf;
    uf.init(n);
    vector<pair<pair<int, int>, pair<int, int>>> v(m);
    for(int i = 0; i < m; i++) {
        int x, y, c, t;
        cin >> x >> y >> c >> t;
        v[i] = {{c, t}, {x, y}};
    }
    sort(v.begin(), v.end());
    int g1 = 0, g2 = 0;
    vector<pair<int, int>> ans;
    for(int i = 0; i < m; i++) {
        if(uf.unite(v[i].second.first, v[i].second.second)) {
            ans.push_back(v[i].second);
            g1 += v[i].first.first;
            g2 += v[i].first.second;
        }
    }
    cout << g1 << ' ' << g2 << '\n';
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i].first << ' ' << ans[i].second << '\n';
    }
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 0; i < ans.size(); i++) {
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 45 / 100