제출 #1195996

#제출 시각아이디문제언어결과실행 시간메모리
1195996Pekibantimeismoney (balkan11_timeismoney)C++20
65 / 100
296 ms608 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e4 + 5; array<int, 4> e[N]; struct DSU { int p[N], sz[N]; void init(int n) { fill(sz+1, sz+n+1, 1); iota(p+1, p+n+1, 1); } int get(int u) { if (u == p[u]) return u; return p[u] = get(p[u]); } bool unite(int u, int v) { u = get(u), v = get(v); if (u == v) return 0; if (sz[u] < sz[v]) swap(u, v); sz[u] += sz[v], p[v] = u; return 1; } } D; int n, m; int A, B; long long mn = 1e12; void solve(int x1, int y1, int x2, int y2) { // cout << x1 << ' ' << y1 << "|" << x2 << ' ' << y2 << '\n'; int a = y1 - y2, b = x2 - x1; sort(e+1, e+m+1, [&](array<int, 4> &x, array<int, 4> &y){ return a * x[2] + b * x[3] < a * y[2] + b * y[3]; }); D.init(n); int xo = 0, yo = 0; for (int i = 1; i <= m; ++i) { // if (a == 226) cout << e[i][0] << ' ' << e[i][1] << ' ' << e[i][2] << ' ' << e[i][3] << ' ' << a * e[i][2] + b * e[i][3] << '\n'; if (D.unite(e[i][0], e[i][1])) xo += e[i][2], yo += e[i][3]; } // cout << x1 << 't' << y1 << "|" << x2 << ' ' << y2 << ' ' << xo << ' ' << yo << ' ' << a << ' ' << b << endl; if (xo * 1LL * yo < mn) A = a, B = b, mn = xo * 1LL * yo; if (a * x1 + b * y1 == a * xo + b * yo) return; solve(x1, y1, xo, yo), solve(xo, yo, x2, y2); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; ++i) cin >> e[i][0] >> e[i][1] >> e[i][2] >> e[i][3]; for (int i = 1; i <= m; ++i) e[i][0]++, e[i][1]++; D.init(n); sort(e+1, e+m+1, [&](array<int, 4> &x, array<int, 4> &y){ return x[2] < y[2]; }); int c1 = 0, t1 = 0, c2 = 0, t2 = 0; for (int i = 1; i <= m; ++i) { // cout << e[i][0] << ' ' << e[i][1] << ' ' << e[i][2] << ' ' << e[i][3] << '\n'; if (D.unite(e[i][0], e[i][1])) { c1 += e[i][2], t1 += e[i][3]; } } D.init(n); sort(e+1, e+m+1, [&](array<int, 4> &x, array<int, 4> &y){ return x[3] < y[3]; }); for (int i = 1; i <= m; ++i) { if (D.unite(e[i][0], e[i][1])) c2 += e[i][2], t2 += e[i][3]; } // cout << c1 << ' ' << t1 << ' ' << c2 << ' ' << t2 << endl; solve(c1, t1, c2, t2); // cout << A << ' ' << B << ' ' << mn << '\n'; sort(e+1, e+m+1, [&](array<int, 4> &x, array<int, 4> &y){ return A * x[2] + B * x[3] < A * y[2] + B * y[3]; }); vector<array<int, 2>> ans; int C = 0, T = 0; D.init(n); for (int i = 1; i <= m; ++i) { if (D.unite(e[i][0], e[i][1])) C += e[i][2], T += e[i][3], ans.push_back({e[i][0], e[i][1]}); } cout << C << ' ' << T << '\n'; for (auto [u, v] : ans) cout << u-1 << ' ' << v-1 << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...