| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 640861 | SanguineChameleon | timeismoney (balkan11_timeismoney) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// BEGIN BOILERPLATE CODE
#include <bits/stdc++.h>
using namespace std;
#ifdef KAMIRULEZ
const bool kami_loc = true;
const long long kami_seed = 69420;
#else
const bool kami_loc = false;
const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif
const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);
long long rand_range(long long rmin, long long rmax) {
uniform_int_distribution<long long> rdist(rmin, rmax);
return rdist(kami_gen);
}
void file_io(string fi, string fo) {
if (fi != "" && (!kami_loc || fi == kami_fi)) {
freopen(fi.c_str(), "r", stdin);
}
if (fo != "" && (!kami_loc || fo == kami_fo)) {
freopen(fo.c_str(), "w", stdout);
}
}
void set_up() {
if (kami_loc) {
file_io(kami_fi, kami_fo);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
}
void just_do_it();
void just_exec_it() {
if (kami_loc) {
auto pstart = chrono::steady_clock::now();
just_do_it();
auto pend = chrono::steady_clock::now();
long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
string bar(50, '=');
cout << '\n' << bar << '\n';
cout << "Time: " << ptime << " ms" << '\n';
}
else {
just_do_it();
}
}
int main() {
set_up();
just_exec_it();
return 0;
}
// END BOILERPLATE CODE
// BEGIN MAIN CODE
const int ms = 1e4 + 20;
const int st = 2e2 + 20;
int de[st];
int par[st];
long long res = (long long)1e18 + 20;
long long fa;
long long fb;
int n, m;
struct point {
long long x, y;
};
point fp;
int root(int u) {
if (!par[u]) {
return u;
}
return root(par[u]);
}
bool update(int u, int v) {
int ru = root(u);
int rv = root(v);
if (ru == rv) {
return false;
}
if (de[ru] > de[rv]) {
swap(ru, rv);
}
par[ru] = rv;
if (de[ru] == de[rv]) {
de[rv]++;
}
return true;
}
struct edge {
int u, v;
long long x, y;
};
struct cmp {
long long pa;
long long pb;
cmp(long long a, long long b) {
pa = a;
pb = b;
}
bool operator()(edge e1, edge e2) {
return e1.x * pa + e1.y * pb < e2.x * pa + e2.y * pb;
}
};
edge e[ms];
point mst(long long a, long long b, bool f = false) {
long long sx = 0;
long long sy = 0;
for (int i = 0; i < n; i++) {
de[i] = 0;
par[i] = 0;
}
sort(e, e + m, cmp(a, b));
for (int i = 0; i < m; i++) {
int u = e[i].u;
int v = e[i].v;
if (update(u, v)) {
if (f) {
cout << u << " " << v << '\n';
}
sx += e[i].x;
sy += e[i].y;
}
}
long long cr = sx * sy;
if (cr < res) {
res = cr;
fp = point(sx, sy);
fa = a;
fb = b;
}
return point(sx, sy);
}
void solve(point p1, point p2) {
if (p1.x == p2.x || p1.y == p2.y) {
return;
}
long long dx = p2.x - p1.x;
long long dy = p1.y - p2.y;
point p3 = mst(dy, dx);
if ((p1.y - p2.y) * (p3.x - p1.x) == (p1.y - p3.y) * (p2.x - p1.x)) {
return;
}
solve(p1, p3);
solve(p3, p2);
}
void just_do_it() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> e[i].u >> e[i].v >> e[i].x >> e[i].y;
}
solve(mst(1, 0), mst(0, 1));
cout << fp.x << " " << fp.y << '\n';
mst(fa, fb, 1);
}
// END MAIN CODE