Submission #1286731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286731		LIA	시간이 돈 (balkan11_timeismoney)	C++17	0 / 100	1 ms	1092 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
struct Dsu {
  vll p, sz;

  Dsu(ll n) : p(n), sz(n, 1) {
    iota(p.begin(), p.end(), 0);
  }

  ll find(ll v) {
    if (p[v] == v)
      return v;
    return p[v] = find(p[v]);
  }

  bool uni(ll a, ll b) {
    ll x = find(a), y = find(b);
    if (x == y)
      return 0;
    if (sz[x] < sz[y])
      swap(x, y);
    sz[x] += sz[y];
    p[y] = x;
    return 1;
  }
};

int main() {
  if (!freopen("timeismoney.in", "r", stdin)) return 0;
  if (!freopen("timeismoney.out", "w", stdout)) return 0;

  ll n, m;
  cin >> n >> m;
  vector<tuple<ll, ll, ll>> vec;

  for (ll i = 0; i < m; ++i) {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    vec.push_back({c, a, b});
  }

  sort(vec.begin(), vec.end());
  Dsu dsu(n + 1);
  ll sum = 0;
  vector<pair<ll, ll>> pairs;
  for (auto [c, a, b] : vec) {
    if (dsu.uni(a, b)) {
      sum += c;
      pairs.push_back({a, b});
    }
  }
  cout << sum << " " << sum << "\n";
  for (auto [a, b] : pairs)
    cout << a << " " << b << "\n";
}

• Subtask 1: 0 / 100