Submission #928364

#	Time	Username	Problem	Language	Result	Execution time	Memory
928364		Kripton	timeismoney (balkan11_timeismoney)	C++17	65 / 100	2068 ms	604 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;

struct mazan{
    int x, y, c, t;
}much[10001];

long double x;
const long double eps = 1e-9;

bool cmp(mazan a, mazan b)
{
    return x * a.c + (1.00 - x) * a.t < x * b.c + (1.00 - x) * b.t - eps;
}

int tata[201], sz[201];

int papa(int nod)
{
    if(tata[nod] == nod)
        return nod;
    return tata[nod] = papa(tata[nod]);
}

int sumT, sumC;
pair <int, int> afis[201], acum[201];
int cnt1;

void join(int a, int b, int c, int t)
{
    int ra = papa(a), rb = papa(b);
    if(ra == rb)
        return;
    if(sz[ra] < sz[rb])
        swap(ra, rb);
    tata[rb] = ra;
    sz[ra] += sz[rb];
    sumC += c;
    sumT += t;
    acum[++cnt1] = {a, b};
}

int main()
{
#ifdef HOME
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif // HOME
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> much[i].x >> much[i].y >> much[i].c >> much[i].t;
    long double BULAN = (1.00 / (1 << 16));
    long long min1 = LLONG_MAX;
    int afisT, afisC;
    for(x = 0; x < 1 - eps; x += BULAN)
    {
        sumT = sumC = 0;
        cnt1 = 0;
        sort(much + 1, much + m + 1, cmp);
        for(int i = 0; i < n; i++)
        {
            tata[i] = i;
            sz[i] = 0;
        }
        for(int i = 1; i <= m; i++)
            join(much[i].x, much[i].y, much[i].c, much[i].t);
        if(1LL * sumT * sumC < min1)
        {
            min1 = 1LL * sumT * sumC;
            afisT = sumT;
            afisC = sumC;
            for(int i = 1; i < n; i++)
                afis[i] = acum[i];
        }
    }
    cout << afisC << " " << afisT << '\n';
    for(int i = 1; i < n; i++)
        cout << afis[i].first << " " << afis[i].second << '\n';
    return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:77:22: warning: 'afisC' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |     cout << afisC << " " << afisT << '\n';
      |                      ^~~
timeismoney.cpp:77:38: warning: 'afisT' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |     cout << afisC << " " << afisT << '\n';
      |                                      ^~~~

• Subtask 1: 65 / 100