Submission #1001221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001221		andrei_iorgulescu	timeismoney (balkan11_timeismoney)	C++14	95 / 100	1403 ms	1116 KiB

timeismoney

#include <bits/stdc++.h>

using namespace std;

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 <= 25; r1++)
    {
        for (int r2 = 1; r2 <= 25; r2++)
        {
            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;
        }
    }
    srand(time(NULL));
    vector<int> f1,f2;
    for (int i = 1; i <= 30; i++)
        f1.push_back(rand() % 256 + 1),f2.push_back(rand() % 256 + 1);
    for (auto r1 : f1)
    {
        for (auto r2 : f2)
        {
            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: 95 / 100