# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1010555 | vjudge1 | timeismoney (balkan11_timeismoney) | C++17 | 2024 ms | 2784 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.
// ^^
// <{:3
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
//#define int long signed long int
#define ld long double
using namespace std;
const int maxn = 202;
vector<tuple<ld, ld, int, int>> edges; // c t x y
pair<int, ld> ans; // val, k
int p[maxn];
int n, m;
inline void rt() { for(int i = 0; i <= n; ++i) p[i] = i; }
int f(int x)
{
if(p[x] == x) return x;
return p[x] = f(p[x]);
}
inline void u(int x, int y)
{
x = f(x); y = f(y);
if(x == y) return;
p[x] = y;
}
pair<int, int> mst(ld k)
{
vector<tuple<ld, ld, ld, int, int>> v;
rt();
for(auto [c, t, x, y] : edges) v.emplace_back(t+k*c, c, t, x, y);
sort(v.begin(), v.end());
pair<int, int> ret(0, 0);
for(auto [val, c, t, x, y] : v)
{
if(f(x) != f(y))
{
ret.first += c;
ret.second += t;
u(x, y);
}
}
return ret;
}
void rec(ld x1, ld y1, ld x2, ld y2, int dep)
{
if(x1 == x2) return;
//cout << x1 << " " << y1 << " " << x2 << " " << y2 << " bananus" << endl;
if(dep > 10) return;
ld k = (y1 - y2) / (x1 - x2);
ld c = y1 - (k * x1);
pair<int, int> novi = mst(-k);
ld y = (k*novi.first) + c;
//cout << novi.first << " " << novi.second << " " << k << " dbdb\n";
if(novi.second >= y) return;
if(novi.first * novi.second < ans.first)
{
ans.first = novi.first * novi.second;
ans.second = k;
}
rec(x1, y1, novi.first, novi.second, dep+1);
rec(x2, y2, novi.first, novi.second, dep+1);
}
signed main()
{
cin.tie(NULL)->sync_with_stdio(false);
//freopen("10-timeismoney.in", "r", stdin);
ans = {1e9, 0};
cin >> n >> m;
for(int i = 0; i < m; ++i)
{
ld t, c;
int x, y;
cin >> x >> y >> t >> c;
edges.emplace_back(t, c, x, y);
}
rt();
vector<pair<int, int>> minte, mince;
sort(edges.begin(), edges.end());
pair<int, int> mint(0, 0);
for(auto &[t, c, x, y] : edges)
{
int xtr = f(x), ytr = f(y);
if(xtr != ytr)
{
mint.first += c;
mint.second += t;
minte.emplace_back(x, y);
u(xtr, ytr);
}
swap(t, c);
}
rt();
sort(edges.begin(), edges.end());
pair<int, int> minc(0, 0);
for(auto &[c, t, x, y] : edges)
{
int xtr = f(x), ytr = f(y);
if(xtr != ytr)
{
minc.first += c;
minc.second += t;
mince.emplace_back(x, y);
u(xtr, ytr);
}
}
rec(minc.first, minc.second, mint.first, mint.second, 0);
if(minc.first * minc.second < ans.first)
{
swap(minc.first, minc.second);
cout << minc.first << " " << minc.second << "\n";
for(auto [x, y] : mince) cout << x << " " << y << "\n";
return 0;
}
if(mint.first * mint.second < ans.first)
{
swap(mint.first, mint.second);
cout << mint.first << " " << mint.second << "\n";
for(auto [x, y] : minte) cout << x << " " << y << "\n";
return 0;
}
rt();
ld k = -ans.second;
vector<tuple<ld, ld, ld, int, int>> v;
for(auto [c, t, x, y] : edges) v.emplace_back(t+k*c, c, t, x, y);
sort(v.begin(), v.end());
pair<int, int> ret(0, 0);
vector<pair<int, int>> ansedge;
for(auto [val, c, t, x, y] : v)
{
if(f(x) != f(y))
{
ret.first += c;
ret.second += t;
u(x, y);
ansedge.emplace_back(x, y);
}
}
swap(ret.first, ret.second);
cout << ret.first << " " << ret.second << "\n";
for(auto [x, y] : ansedge) cout << x << " " << y << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |