oj.uz

Submission #928364

# Submission time Handle Problem Language Result Execution time Memory
928364 2024-02-16T09:13:11 Z Kripton timeismoney (balkan11_timeismoney) C++17
65 / 100
 2000 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 / (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

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

# Verdict Execution time Memory Grader output
1 Correct 491 ms 424 KB Output is correct
2 Correct 25 ms 600 KB Output is correct
3 Correct 36 ms 348 KB Output is correct
4 Correct 156 ms 420 KB Output is correct
5 Correct 1128 ms 428 KB Output is correct
6 Correct 843 ms 428 KB Output is correct
7 Execution timed out 2036 ms 344 KB Time limit exceeded
8 Execution timed out 2068 ms 604 KB Time limit exceeded
9 Correct 25 ms 344 KB Output is correct
10 Correct 69 ms 348 KB Output is correct
11 Correct 36 ms 348 KB Output is correct
12 Correct 162 ms 420 KB Output is correct
13 Correct 158 ms 348 KB Output is correct
14 Correct 1138 ms 432 KB Output is correct
15 Correct 882 ms 428 KB Output is correct
16 Execution timed out 2053 ms 348 KB Time limit exceeded
17 Execution timed out 2017 ms 344 KB Time limit exceeded
18 Execution timed out 2020 ms 476 KB Time limit exceeded
19 Execution timed out 2029 ms 600 KB Time limit exceeded
20 Execution timed out 2067 ms 604 KB Time limit exceeded