Submission #328632

#	Time	Username	Problem	Language	Result	Execution time	Memory
328632		Qingyu	timeismoney (balkan11_timeismoney)	C++17	0 / 100	462 ms	748 KiB

timeismoney

#include <bits/stdc++.h>

const int N = 1e6 + 50;

int n, m;

struct edge_t
{
	int u, v, t1, t2;
} e[N];

struct point_t
{
	int64_t x, y;
	point_t() = default;
	point_t(int x, int y) : x(x), y(y) {}
};

inline bool operator<(const point_t &p, const point_t &q)
{
	int64_t vp = p.x * p.y, vq = q.x * q.y;
	if (vp != vq) return vp < vq;
	return p.x < q.x;
}
inline point_t operator-(const point_t &p, const point_t&q) { return point_t(p.x - q.x, p.y - q.y); }
inline int64_t cross(const point_t &p, const point_t &q) { return p.x * q.y - q.x * p.y; }

auto cmp(int64_t a, int64_t b)
{
	return [=](const edge_t &e1, const edge_t &e2)
	{
		return e1.t1 * a + e1.t2 * b < e2.t1 * a + e2.t2 * b;
	};
}

struct UFS
{
	int f[N];
	inline void reset()
	{
		for (int i = 1; i <= n; ++i) f[i] = i;
	}
	inline int find(int x)
	{
		while (x != f[x]) x = f[x] = f[f[x]];
		return x;
	}
} t;

inline point_t kruskal(int a, int b)
{
	auto z = cmp(a, b);
	std::sort(e + 1, e + m + 1, z);
	t.reset();
	point_t res(0, 0);
	for (int i = 1; i <= m; ++i)
	{
		auto [u, v, t1, t2] = e[i];
		assert(u == e[i].u && v == e[i].v && t1 == e[i].t1 && t2 == e[i].t2);
		u = t.find(u), v = t.find(v);
		if (u != v)
		{
			t.f[u] = v;
			res.x += t1, res.y += t2;
		}
	}
	return res;
}

point_t solve(const point_t &L, const point_t &R)
{
	point_t mid = kruskal(L.y - R.y, R.x - L.x);
	if (cross(R - L, mid - L) < 0)
	{
		return std::min(solve(L, mid), solve(mid, R));
	}
	return std::min(L, R);
}

template<int T>
struct fast_io
{
	char p[T], q[T], *p1, *p2, *q1, *q2;

	fast_io()
	{
		p1 = p2 = p;
		q1 = q, q2 = q + T;
	}

	inline char gc()
	{
		return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
	}

	inline void pc(char c)
	{
		if (q1 == q2) q2 = (q1 = q) + fwrite(q, 1, T, stdout);
		*q1++ = c;
	}

	~fast_io()
	{
		fwrite(q, 1, q1 - q, stdout);
	}
};

fast_io<1 << 20> io;

inline int64_t read()
{
	int64_t res = 0, neg = 1;
	char ch;
	do
	{
		ch = io.gc();
		if (ch == '-') neg = -1;
	} while (ch < 48 || ch > 57);
	do res = res * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
	return res * neg;
}

inline void put(int64_t x)
{
	if (x < 0) io.pc('-'), x = -x;
	if (x >= 10) put(x / 10);
	io.pc(48 + x % 10);
}

inline void output(int64_t x, char ch = ' ')
{
	put(x);
	io.pc(ch);
}


int main()
{
	n = read(), m = read();
	for (int i = 1; i <= m; ++i)
	{
		e[i].u = read() + 1, e[i].v = read() + 1, e[i].t1 = read(), e[i].t2 = read();
	}
	auto p = kruskal(1, 0);
	auto q = kruskal(0, 1);
	auto answer = solve(p, q);
	output(answer.x); output(answer.y);
}

• Subtask 1: 0 / 100