oj.uz

Submission #928368

# Submission time Handle Problem Language Result Execution time Memory
928368 2024-02-16T09:14:47 Z Kripton timeismoney (balkan11_timeismoney) C++17
100 / 100
 408 ms 604 KB 
#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 / 400);
    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

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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 8 ms 444 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 42 ms 448 KB Output is correct
8 Correct 221 ms 564 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 10 ms 344 KB Output is correct
15 Correct 8 ms 348 KB Output is correct
16 Correct 63 ms 344 KB Output is correct
17 Correct 63 ms 344 KB Output is correct
18 Correct 68 ms 348 KB Output is correct
19 Correct 404 ms 344 KB Output is correct
20 Correct 408 ms 604 KB Output is correct