# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1001206 | andrei_iorgulescu | timeismoney (balkan11_timeismoney) | C++14 | 2087 ms | 1564 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
int idx[300][300];
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;
idx[a[i].x][a[i].y] = i;
}
for (int r1 = 1; r1 <= 256; r1++)
{
for (int r2 = 1; r2 <= 256; r2++)
{
if (r1 >= 5 and r2 >= 5 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)
{
int cn = idx[it.first][it.second];
cur.use[cn] = true;
cur.sumtime += a[cn].t;
cur.summoney += a[cn].c;
}
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |