답안 #488719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
488719 2021-11-20T07:47:52 Z InternetPerson10 시간이 돈 (balkan11_timeismoney) C++17
45 / 100
5 ms 592 KB
#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

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++) {
      |                    ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 220 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Incorrect 1 ms 208 KB Output isn't correct
11 Incorrect 0 ms 208 KB Output isn't correct
12 Incorrect 0 ms 208 KB Output isn't correct
13 Incorrect 1 ms 208 KB Output isn't correct
14 Incorrect 1 ms 208 KB Output isn't correct
15 Incorrect 1 ms 316 KB Output isn't correct
16 Incorrect 1 ms 336 KB Output isn't correct
17 Incorrect 1 ms 336 KB Output isn't correct
18 Incorrect 2 ms 336 KB Output isn't correct
19 Incorrect 5 ms 592 KB Output isn't correct
20 Incorrect 4 ms 580 KB Output isn't correct