Submission #1001176

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1001176	2024-06-18T16:33:23 Z	andrei_iorgulescu	timeismoney (balkan11_timeismoney)	C++14	50 / 100	2000 ms	65536 KB

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);
            }
        }
    }
    rate.push_back(1);
    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

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	7 ms	860 KB	Output is correct
8	Correct	115 ms	2720 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Incorrect	1 ms	348 KB	Output isn't correct
11	Incorrect	1 ms	348 KB	Output isn't correct
12	Incorrect	7 ms	348 KB	Output isn't correct
13	Correct	8 ms	348 KB	Output is correct
14	Incorrect	1327 ms	988 KB	Output isn't correct
15	Incorrect	677 ms	860 KB	Output isn't correct
16	Execution timed out	2029 ms	9928 KB	Time limit exceeded
17	Execution timed out	2040 ms	10452 KB	Time limit exceeded
18	Execution timed out	2029 ms	10440 KB	Time limit exceeded
19	Runtime error	76 ms	65536 KB	Execution killed with signal 9
20	Runtime error	95 ms	65536 KB	Execution killed with signal 9