# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
480868 | duchung | timeismoney (balkan11_timeismoney) | C++17 | 269 ms | 1352 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
#define double long double
#define ii pair<int , int>
#define dd pair<double , double>
#define iiii pair<ii , dd>
const int N = 205;
const double EPS = 1e-9;
int n , m;
vector<iiii> edges;
double tmp , slope;
int parent[N] , level[N];
double val(iiii tmp)
{
return slope * tmp.second.first + (1 - slope) * tmp.second.second;
}
bool cmp(iiii x , iiii y)
{
return val(x) + EPS < val(y);
}
int find_set(int u)
{
return u == parent[u] ? u : parent[u] = find_set(parent[u]);
}
bool union_set(int u , int v)
{
u = find_set(u);
v = find_set(v);
if (u == v) return false;
if (level[u] < level[v]) swap(u , v);
parent[v] = u;
if (level[u] == level[v]) ++level[u];
return true;
}
int solve(double cur)
{
slope = cur;
sort(edges.begin() , edges.end() , cmp);
for (int i = 0 ; i < n ; ++i) parent[i] = i;
memset(level , 0 , sizeof(level));
int sumT = 0 , sumC = 0;
for (auto x : edges)
{
int u = x.first.first;
int v = x.first.second;
int t = x.second.first;
int c = x.second.second;
if (union_set(u , v))
{
sumT += t;
sumC += c;
}
}
return sumT * sumC;
}
void print(double cur)
{
slope = cur;
sort(edges.begin() , edges.end() , cmp);
for (int i = 0 ; i < n ; ++i) parent[i] = i;
memset(level , 0 , sizeof(level));
int sumT = 0 , sumC = 0;
vector<pair<int , int>> ans;
for (auto x : edges)
{
int u = x.first.first;
int v = x.first.second;
int t = x.second.first;
int c = x.second.second;
if (union_set(u , v))
{
sumT += t;
sumC += c;
ans.push_back({u , v});
}
}
cout << sumT << " " << sumC << "\n";
for (auto x : ans) cout << x.first << " " << x.second << "\n";
}
signed main()
{
// freopen(".inp","r",stdin);
// freopen(".out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
while(m--)
{
int u , v , t , c;
cin >> u >> v >> t >> c;
edges.push_back({{u , v} , {t , c}});
}
double l = 0 , r = 1;
while(r - l > 1e-8)
{
double lm = l + (r - l) / 3;
double rm = r - (r - l) / 3;
if (solve(lm) > solve(rm))
{
l = lm;
}
else
{
r = rm;
}
// cerr << l << " " << r << "\n";
}
if (solve(l) > solve(r))
{
print(r);
}
else
{
print(l);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |