Submission #999473

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
999473	2024-06-15T14:35:02 Z	Andrei_ierdnA	timeismoney (balkan11_timeismoney)	C++17	100 / 100	167 ms	604 KB

timeismoney

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 200
#define MAXM 10000
#define BULAN 1

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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	3 ms	476 KB	Output is correct
6	Correct	2 ms	348 KB	Output is correct
7	Correct	13 ms	532 KB	Output is correct
8	Correct	74 ms	600 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	4 ms	348 KB	Output is correct
15	Correct	4 ms	348 KB	Output is correct
16	Correct	26 ms	348 KB	Output is correct
17	Correct	26 ms	348 KB	Output is correct
18	Correct	25 ms	536 KB	Output is correct
19	Correct	163 ms	604 KB	Output is correct
20	Correct	167 ms	604 KB	Output is correct