Submission #1001201

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1001201	2024-06-18T16:56:57 Z	andrei_iorgulescu	timeismoney (balkan11_timeismoney)	C++14	95 / 100	1698 ms	3100 KB

timeismoney

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct edge
{
    int x,y,t,c;
};

int n,m;
edge a[10005];
vector<pair<int,pair<int,int>>> e;
map<pair<int,int>,int> timp, cost, idx;

struct sol
{
    vector<bool> use;
    int v,sumtime,summoney;
};

sol ans;

int tt[205],sz[205];

int rep(int x)
{
    while (x != tt[x])
        x = tt[x];
    return x;
}

void join(int x,int y)
{
    x = rep(x);
    y = rep(y);
    if (x == y)
        return;
    if (sz[x] < sz[y])
        swap(x,y);
    sz[x] += sz[y];
    tt[y] = x;
}

signed main()
{
    ans.v = ans.sumtime = 1e9;
    ans.summoney = 1;
    cin >> n >> m;
    ans.use.resize(m + 1);
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i].x >> a[i].y >> a[i].t >> a[i].c;
        timp[ {a[i].x,a[i].y}] = a[i].t;
        cost[ {a[i].x,a[i].y}] = a[i].c;
        idx[ {a[i].x,a[i].y}] = i;
    }
    for (int r1 = 1; r1 <= 256; r1++)
    {
        for (int r2 = 1; r2 <= 256; r2++)
        {
            if (r1 >= 3 and r2 >= 3 and (r1 + r2) % 100 != 0)
                continue;
            e.clear();
            for (int i = 1; i <= m; i++)
            {
                int x = a[i].x,y = a[i].y;
                int cost = a[i].c * r1 + a[i].t * r2;
                e.push_back({cost,{x,y}});
            }
            sort(e.begin(),e.end());
            for (int i = 0; i < n; i++)
                tt[i] = i,sz[i] = 1;
            vector<pair<int,int>> luate;
            for (auto it : e)
            {
                if (rep(it.second.first) != rep(it.second.second))
                {
                    luate.push_back(it.second);
                    join(it.second.first,it.second.second);
                }
            }
            sol cur;
            cur.use.resize(m + 1);
            cur.summoney = cur.sumtime = 0;
            for (auto it : luate)
            {
                cur.use[idx[it]] = true;
                cur.sumtime += timp[it];
                cur.summoney += cost[it];
            }
            cur.v = cur.sumtime * cur.summoney;
            if (cur.v < ans.v)
                ans = cur;
        }
    }
    cout << ans.sumtime << ' ' << ans.summoney << '\n';
    for (int i = 1; i <= m; i++)
        if (ans.use[i])
            cout << a[i].x << ' ' << a[i].y << '\n';
    return 0;
}

Subtask #1

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	500 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	2 ms	452 KB	Output is correct
4	Correct	9 ms	348 KB	Output is correct
5	Correct	27 ms	556 KB	Output is correct
6	Correct	31 ms	348 KB	Output is correct
7	Correct	214 ms	1104 KB	Output is correct
8	Correct	1698 ms	3096 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	3 ms	348 KB	Output is correct
11	Correct	3 ms	344 KB	Output is correct
12	Correct	7 ms	468 KB	Output is correct
13	Correct	8 ms	468 KB	Output is correct
14	Correct	41 ms	348 KB	Output is correct
15	Correct	62 ms	348 KB	Output is correct
16	Correct	300 ms	856 KB	Output is correct
17	Correct	274 ms	952 KB	Output is correct
18	Correct	277 ms	860 KB	Output is correct
19	Correct	1483 ms	3100 KB	Output is correct
20	Incorrect	1452 ms	3100 KB	Output isn't correct