# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
999469 | Andrei_ierdnA | timeismoney (balkan11_timeismoney) | C++17 | 1796 ms | 756 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.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 200
#define MAXM 10000
#define BULAN 10
struct Edge
{
int index, x, y;
long long t, c;
int other(int node)
{
return (node == x) ? y : x;
}
static bool indexCmp(const Edge &a, const Edge &b)
{
return (a.index < b.index);
}
};
struct Apm
{
long long t = 10000000, c = 10000000;
int eid[MAXN+3];
bool operator < (const Apm &other) const
{
return t * c < other.t * other.c;
}
};
struct Dsu
{
int p[MAXN+3], nrdsu;
void init(int n)
{
nrdsu = n;
for (int i = 1; i <= n; i++) {
p[i] = -1;
}
}
int getRoot(int node)
{
if (p[node] < 0) return node;
return p[node] = getRoot(p[node]);
}
bool dsuMerge(int a, int b)
{
a = getRoot(a);
b = getRoot(b);
if (a == b) return false;
if (p[a] > p[b]) swap(a, b);
p[a] += p[b];
p[b] = a;
nrdsu--;
return true;
}
} dsu;
long long tm = 1, cm = 1;
int n, m;
Edge edges[MAXM+5];
Apm apms[2];
int ansapm = 0;
bool operator < (const Edge &a, const Edge &b)
{
return (a.t - b.t) * tm + (a.c - b.c) * cm < 0;
}
void genApm(Apm &apm)
{
sort(edges+1, edges+m+1);
apm.t = apm.c = 0;
dsu.init(n);
int k = 0;
for (int i = 1; k < n-1; i++) {
if (dsu.dsuMerge(edges[i].x, edges[i].y)) {
apm.t += edges[i].t;
apm.c += edges[i].c;
apm.eid[++k] = edges[i].index;
}
}
}
void advanceAns(int steps)
{
for (int cnt = 1; cnt <= steps; cnt++) {
genApm(apms[ansapm^1]);
tm = apms[ansapm^1].c;
cm = apms[ansapm^1].t;
if (apms[ansapm^1] < apms[ansapm]) {
ansapm ^= 1;
}
}
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
edges[i].index = i;
cin >> edges[i].x >> edges[i].y;
edges[i].x++;
edges[i].y++;
cin >> edges[i].t >> edges[i].c;
}
for (int i = 1; i <= 255; i++) {
tm = i, cm = 255;
advanceAns(BULAN);
}
for (int i = 1; i <= 255; i++) {
tm = 255, cm = i;
advanceAns(BULAN);
}
sort(edges+1, edges+m+1, Edge::indexCmp);
cout << apms[ansapm].t << ' ' << apms[ansapm].c << '\n';
for (int i = 1; i < n; i++) {
cout << edges[apms[ansapm].eid[i]].x - 1 << ' ' << edges[apms[ansapm].eid[i]].y - 1 << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |