Submission #999469

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
999469	2024-06-15T14:33:20 Z	Andrei_ierdnA	timeismoney (balkan11_timeismoney)	C++17	100 / 100	1796 ms	756 KB

timeismoney

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	4 ms	468 KB	Output is correct
5	Correct	25 ms	348 KB	Output is correct
6	Correct	20 ms	348 KB	Output is correct
7	Correct	122 ms	348 KB	Output is correct
8	Correct	717 ms	752 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	3 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	5 ms	348 KB	Output is correct
13	Correct	5 ms	348 KB	Output is correct
14	Correct	39 ms	348 KB	Output is correct
15	Correct	28 ms	344 KB	Output is correct
16	Correct	290 ms	348 KB	Output is correct
17	Correct	249 ms	344 KB	Output is correct
18	Correct	286 ms	348 KB	Output is correct
19	Correct	1796 ms	756 KB	Output is correct
20	Correct	1681 ms	600 KB	Output is correct