#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(int a, int 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);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
1 ms |
364 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
1 ms |
364 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
1 ms |
364 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
1 ms |
364 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
1 ms |
364 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
1 ms |
364 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
3 ms |
748 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
1 ms |
364 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
1 ms |
364 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
1 ms |
364 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
1 ms |
364 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
1 ms |
364 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
4 ms |
492 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
3 ms |
364 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
52 ms |
364 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
56 ms |
364 KB |
Unexpected end of file - int32 expected |
| 18 |
Incorrect |
52 ms |
364 KB |
Unexpected end of file - int32 expected |
| 19 |
Incorrect |
451 ms |
876 KB |
Unexpected end of file - int32 expected |
| 20 |
Incorrect |
459 ms |
908 KB |
Unexpected end of file - int32 expected |
