// ^^
// <{: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";
}
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:84:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | freopen("10-timeismoney.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
524 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 11 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 13 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 14 |
Incorrect |
1 ms |
520 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 17 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 18 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 19 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 20 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
