Submission #1170229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170229		ymm	timeismoney (balkan11_timeismoney)	C++20	100 / 100	754 ms	1024 KiB

timeismoney

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

struct DSU {
	vector<int> par;
	void init(int n) { par.assign(n, -1); }
	int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
	bool unite(int v, int u) {
		v = rt(v);
		u = rt(u);
		if (v == u)
			return 0;
		par[u] = v;
		return 1;
	}
};

struct P2 {
	int x, y;

	typedef const P2 &R;
	P2 operator+(R q) const { return {x + q.x, y + q.y}; }
	P2 operator*(int a) const { return {x*a, y*a}; }
	P2 operator-(R q) const { return *this + q*-1; }

	ll dot(R q) const { return (ll)x * q.x + (ll)y * q.y; }
	ll cross(R q) const { return (ll)x * q.y - (ll)y * q.x; }
	P2 normal() const { return {-y, x}; }

	ll val() const { return (ll)x * y; }
	bool operator<(R q) const { return val() < q.val(); }
};

vector<pair<pii,P2>> edges;
vector<pii> solve_edges;
int n;

P2 solve(P2 v)
{
	vector<pair<ll,int>> e;
	Loop (i,0,edges.size()) {
		auto u = edges[i].second;
		e.push_back({v.dot(u), i});
	}
	sort(e.begin(), e.end());
	DSU dsu;
	dsu.init(n);
	solve_edges.clear();
	int sx = 0, sy = 0;
	for (auto [w, i] : e) {
		auto [a, b] = edges[i].first;
		auto [x, y] = edges[i].second;
		if (dsu.unite(a, b)) {
			sx += x;
			sy += y;
			solve_edges.emplace_back(a, b);
		}
	}
	return {sx, sy};
}

ostream &operator<<(ostream &s, P2 p) {
	return s << '(' << p.x << ',' << p.y << ')';
}

pair<P2,P2> dc(pair<P2,P2> pnl, pair<P2,P2> pnr)
{
	auto pl = pnl.first;
	auto pr = pnr.first;
	//cerr << pl << ' ' << pr << '\n';
	if (pl.x == pr.x && pl.y == pr.y)
		return pnl;
	P2 n = (pr - pl).normal();
	P2 p = solve(n);
	pair<P2,P2> pn = {p, n};
	if ((pr - p).cross(pl - p) == 0)
		return min(pnl, pnr);
	return min(dc(pnl, pn), dc(pn, pnr));
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int m;
	cin >> n >> m;
	Loop (i,0,m) {
		int v, u, x, y;
		cin >> v >> u >> x >> y;
		edges.push_back({{v, u}, {x, y}});
	}
	P2 pl = solve({1,0});
	P2 pr = solve({0,1});
	auto [ans, nr] = dc({pl,{1,0}}, {pr,{0,1}});
	cout << ans.x << ' ' << ans.y << '\n';
	solve(nr);
	for (auto [v, u] : solve_edges)
		cout << v << ' ' << u << '\n';
}

• Subtask 1: 100 / 100