oj.uz

답안 #1001182

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1001182 2024-06-18T16:37:46 Z andrei_iorgulescu 시간이 돈 (balkan11_timeismoney) C++14
40 / 100
 2000 ms 3100 KB 
#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++)
        {
            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
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 869 ms 348 KB Output is correct
2 Correct 39 ms 344 KB Output is correct
3 Correct 72 ms 348 KB Output is correct
4 Correct 242 ms 344 KB Output is correct
5 Correct 1028 ms 532 KB Output is correct
6 Correct 1160 ms 508 KB Output is correct
7 Execution timed out 2072 ms 860 KB Time limit exceeded
8 Execution timed out 2067 ms 3100 KB Time limit exceeded
9 Correct 43 ms 344 KB Output is correct
10 Incorrect 78 ms 348 KB Output isn't correct
11 Incorrect 80 ms 448 KB Output isn't correct
12 Incorrect 282 ms 436 KB Output isn't correct
13 Correct 288 ms 344 KB Output is correct
14 Incorrect 1697 ms 532 KB Output isn't correct
15 Incorrect 1669 ms 344 KB Output isn't correct
16 Execution timed out 2061 ms 860 KB Time limit exceeded
17 Execution timed out 2073 ms 860 KB Time limit exceeded
18 Execution timed out 2068 ms 860 KB Time limit exceeded
19 Execution timed out 2071 ms 3100 KB Time limit exceeded
20 Execution timed out 2017 ms 3096 KB Time limit exceeded