Submission #1001174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001174		andrei_iorgulescu	timeismoney (balkan11_timeismoney)	C++14	10 / 100	2072 ms	65536 KiB

timeismoney

#include <bits/stdc++.h>

using namespace std;

const double eps = 0.0001d;

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

int n,m;
edge a[10005];
vector<pair<double,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;
}

int 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;
    }
    vector<double> rate;
    for (int i = 1; i <= m; i++)
    {
        for (int j = i + 1; j <= m; j++)
        {
            if (a[i].c < a[j].c and a[i].t > a[j].t)
            {
                double its = (double)(a[j].c - a[i].t) / (double)(a[i].t - a[j].t);
                rate.push_back(its - eps);
                rate.push_back(its + eps);
            }
        }
    }
    for (auto rata : rate)
    {
        e.clear();
        for (int i = 1; i <= m; i++)
        {
            int x = a[i].x,y = a[i].y;
            double cost = (double)a[i].c + rata * (double)a[i].t;
            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: 10 / 100