제출 #1223013

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223013		adaawf	시간이 돈 (balkan11_timeismoney)	C++20	100 / 100	897 ms	1344 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
struct pt{
    long long int x, y;
    pt operator + (const pt & p) const {
        return pt{x + p.x, y + p.y};
    }
    pt operator - (const pt & p) const {
        return pt{x - p.x, y - p.y};
    }
    __int128 cross(const pt & p) const {
        return (__int128)x * p.y - (__int128)y * p.x;
    }
};
struct EDGE {
    long long int u, v, w, x, y;
};
vector<EDGE> e, ans;
int n, m, p[205], s[205];
long long int mi = 1e18, mix = 1e18, miy = 0;
bool cmp(EDGE aa, EDGE bb) {
    return aa.w < bb.w;
}
int Find(int x) {
    if (x == p[x]) return x;
    return p[x] = Find(p[x]);
}
void Merge(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;
    if (s[x] > s[y]) swap(x, y);
    p[x] = y;
    s[y] += s[x];
}
pt krusk(long long int x, long long int y) {
    vector<EDGE> v = e, vv;
    for (int i = 0; i < v.size(); i++) {
        v[i].w = v[i].x * x + v[i].y * y;
    }
    for (int i = 1; i <= n; i++) p[i] = i, s[i] = 1;
    sort(v.begin(), v.end(), cmp);
    pt res = {0, 0};
    for (auto w : v) {
        if (Find(w.u) != Find(w.v)) {
            Merge(w.u, w.v);
            res.x += w.x;
            res.y += w.y;
            vv.push_back(w);
        }
    }
    if (mi > res.x * res.y) {
        mi = res.x * res.y;
        mix = res.x; miy = res.y;
        ans = vv;
    }
    else if (res.x * res.y == mi && res.x < mix) {
        ans = vv;
        mix = res.x; miy = res.y;
    }
    return res;
}
map<pair<long long int, long long int>, int> mm;
void trya(pt a, pt b) {
    pt h = krusk(a.y - b.y, b.x - a.x);
    if (mm.count({h.x, h.y})) return;
    mm[{h.x, h.y}] = 1;
    if ((b - a).cross(h - a) < 0) {
        trya(a, h);
        trya(h, b);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, x, y;
        cin >> u >> v >> x >> y;
        e.push_back({u + 1, v + 1, 0, x, y});
    }
    pt a = krusk(1, 0), b = krusk(0, 1);
    trya(a, b);
    cout << mix << " " << miy << '\n';
    for (auto w : ans) cout << w.u - 1 << " " << w.v - 1 << '\n';
}

• Subtask 1: 100 / 100