Submission #999468

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
999468	2024-06-15T14:31:28 Z	Andrei_ierdnA	timeismoney (balkan11_timeismoney)	C++17	90 / 100	2000 ms	752 KB

timeismoney

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

using namespace std;

#define MAXN 200
#define MAXM 10000
#define BULAN 20

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()
{
    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;
        for (int j = 1; j <= BULAN; j++) {
            advanceAns();
        }
    }
    for (int i = 1; i <= 255; i++) {
        tm = 255, cm = i;
        for (int j = 1; j <= BULAN; j++) {
            advanceAns();
        }
    }
    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

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	348 KB	Output is correct
2	Correct	2 ms	348 KB	Output is correct
3	Correct	3 ms	348 KB	Output is correct
4	Correct	9 ms	348 KB	Output is correct
5	Correct	49 ms	348 KB	Output is correct
6	Correct	38 ms	344 KB	Output is correct
7	Correct	280 ms	348 KB	Output is correct
8	Correct	1451 ms	752 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	4 ms	464 KB	Output is correct
11	Correct	3 ms	348 KB	Output is correct
12	Correct	9 ms	348 KB	Output is correct
13	Correct	9 ms	348 KB	Output is correct
14	Correct	79 ms	456 KB	Output is correct
15	Correct	51 ms	348 KB	Output is correct
16	Correct	484 ms	348 KB	Output is correct
17	Correct	390 ms	600 KB	Output is correct
18	Correct	505 ms	348 KB	Output is correct
19	Execution timed out	2067 ms	604 KB	Time limit exceeded
20	Execution timed out	2073 ms	604 KB	Time limit exceeded