답안 #1001198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001198	2024-06-18T16:55:38 Z	andrei_iorgulescu	시간이 돈 (balkan11_timeismoney)	C++14	85 / 100	2000 ms	3096 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;
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;
}

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;
        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 r1 = 1; r1 <= 256; r1++)
    {
        for (int r2 = 1; r2 <= 256; r2++)
        {
            if (r1 >= 6 and r2 >= 6 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)
            {
                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

85.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	348 KB	Output is correct
2	Correct	3 ms	348 KB	Output is correct
3	Correct	3 ms	348 KB	Output is correct
4	Correct	12 ms	464 KB	Output is correct
5	Correct	52 ms	532 KB	Output is correct
6	Correct	58 ms	348 KB	Output is correct
7	Correct	400 ms	948 KB	Output is correct
8	Execution timed out	2050 ms	3096 KB	Time limit exceeded
9	Correct	2 ms	348 KB	Output is correct
10	Correct	4 ms	348 KB	Output is correct
11	Correct	4 ms	452 KB	Output is correct
12	Correct	13 ms	348 KB	Output is correct
13	Correct	14 ms	460 KB	Output is correct
14	Correct	82 ms	532 KB	Output is correct
15	Correct	82 ms	344 KB	Output is correct
16	Correct	499 ms	856 KB	Output is correct
17	Correct	533 ms	856 KB	Output is correct
18	Correct	527 ms	856 KB	Output is correct
19	Execution timed out	2084 ms	3096 KB	Time limit exceeded
20	Execution timed out	2083 ms	3096 KB	Time limit exceeded