Submission #1001170

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1001170	2024-06-18T16:25:17 Z	andrei_iorgulescu	timeismoney (balkan11_timeismoney)	C++14	50 / 100	415 ms	2904 KB

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;
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;
    }
    for (int rata = 1; rata <= 200; rata++)
    {
        e.clear();
        for (int i = 1; i <= m; i++)
        {
            int x = a[i].x,y = a[i].y;
            int cost = a[i].c + rata * 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;
    }
    for (int rata = 1; rata <= 200; rata++)
    {
        e.clear();
        for (int i = 1; i <= m; i++)
        {
            int x = a[i].x,y = a[i].y;
            int cost = a[i].c * rata + 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	7 ms	444 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	2 ms	348 KB	Output is correct
5	Correct	6 ms	488 KB	Output is correct
6	Correct	8 ms	348 KB	Output is correct
7	Correct	54 ms	860 KB	Output is correct
8	Correct	415 ms	2904 KB	Output is correct
9	Correct	1 ms	348 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	2 ms	476 KB	Output isn't correct
13	Correct	2 ms	348 KB	Output is correct
14	Incorrect	9 ms	548 KB	Output isn't correct
15	Incorrect	9 ms	348 KB	Output isn't correct
16	Incorrect	63 ms	712 KB	Output isn't correct
17	Incorrect	65 ms	860 KB	Output isn't correct
18	Incorrect	64 ms	904 KB	Output isn't correct
19	Incorrect	384 ms	2904 KB	Output isn't correct
20	Incorrect	368 ms	2904 KB	Output isn't correct