Submission #1001208

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1001208	2024-06-18T16:59:43 Z	andrei_iorgulescu	timeismoney (balkan11_timeismoney)	C++14	90 / 100	2000 ms	1824 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;
int idx[300][300];

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;
        idx[a[i].x][a[i].y] = i;
    }
    for (int r1 = 1; r1 <= 256; r1++)
    {
        for (int r2 = 1; r2 <= 256; r2++)
        {
            if (r1 >= 4 and r2 >= 4 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)
            {
                int cn = idx[it.first][it.second];
                cur.use[cn] = true;
                cur.sumtime += a[cn].t;
                cur.summoney += a[cn].c;
            }
            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

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	600 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	2 ms	344 KB	Output is correct
4	Correct	4 ms	348 KB	Output is correct
5	Correct	26 ms	720 KB	Output is correct
6	Correct	20 ms	880 KB	Output is correct
7	Correct	126 ms	856 KB	Output is correct
8	Execution timed out	2025 ms	1824 KB	Time limit exceeded
9	Correct	2 ms	348 KB	Output is correct
10	Correct	4 ms	348 KB	Output is correct
11	Correct	3 ms	348 KB	Output is correct
12	Correct	6 ms	348 KB	Output is correct
13	Correct	6 ms	348 KB	Output is correct
14	Correct	38 ms	604 KB	Output is correct
15	Correct	30 ms	876 KB	Output is correct
16	Correct	307 ms	1076 KB	Output is correct
17	Correct	296 ms	1080 KB	Output is correct
18	Correct	322 ms	1076 KB	Output is correct
19	Correct	1808 ms	1824 KB	Output is correct
20	Incorrect	1807 ms	1820 KB	Output isn't correct