Submission #1195996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195996		Pekiban	timeismoney (balkan11_timeismoney)	C++20	65 / 100	296 ms	608 KiB

timeismoney

#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';
    
}

• Subtask 1: 65 / 100