제출 #235326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235326		jhnah917	시간이 돈 (balkan11_timeismoney)	C++14	100 / 100	492 ms	768 KiB

timeismoney

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

p operator - (const p a, const p b){return p(a.x - b.x, a.y - b.y); }
struct Edge{
	ll s, e, x, y;
	Edge() : Edge(0, 0, 0, 0) {}
	Edge(ll s, ll e, ll x, ll y) : s(s), e(e), x(x), y(y) {}
};
struct UF{
    int par[222];
    void init(){ iota(par, par+222, 0); }
    int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
    bool merge(int u, int v){
        u = find(u), v = find(v);
        if(u == v) return 0;
        par[u] = v; return 1;
    }
} uf;
inline ll ccw(p a, p b, p c){
	p A = b - a, B = c - a;
	return A.x*B.y - A.y*B.x;
}

int n, m;
vector<Edge> edge;
ll mnx, mny;
vector<p> res, now;

p get(ll x, ll y){
    uf.init();
    sort(all(edge), [&](Edge a, Edge b){
        return a.x*x + a.y*y < b.x*x + b.y*y;
    });
    ll s1 = 0, s2 = 0; now.clear();
    for(auto i : edge) if(uf.merge(i.s, i.e)) s1 += i.x, s2 += i.y, now.push_back({i.s, i.e});
    if(s1 * s2 < mnx * mny || res.empty()) mnx = s1, mny = s2, res = now;
    return {s1, s2};
}

void f(p s, p e){
	p m = get(s.y - e.y, e.x - s.x);
    if(ccw(s, m, e) > 0) f(s, m), f(m, e);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m; edge.resize(m);
    for(auto &i : edge) cin >> i.s >> i.e >> i.x >> i.y;

    p s = get(1, 0), e = get(0, 1);
    f(s, e);
    cout << mnx << " " << mny << "\n\n";
    for(auto i : res) cout << i.x << " " << i.y << "\n";
}

• Subtask 1: 100 / 100