// ^^
// <{: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(c+t*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)
{
if(x1 == x2) 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);
rec(novi.first, novi.second, x1, y1);
}
signed main()
{
cin.tie(NULL)->sync_with_stdio(false);
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();
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;
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;
u(xtr, ytr);
}
}
rec(minc.first, minc.second, mint.first, mint.second);
//cout << ans.first << " " << ans.second;
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 |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
3 ms |
860 KB |
Output is correct |
| 8 |
Correct |
10 ms |
2516 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
456 KB |
Output isn't correct |
| 11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 12 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 13 |
Execution timed out |
2098 ms |
39800 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2074 ms |
7372 KB |
Time limit exceeded |
| 15 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 16 |
Incorrect |
3 ms |
860 KB |
Output isn't correct |
| 17 |
Incorrect |
3 ms |
860 KB |
Output isn't correct |
| 18 |
Incorrect |
3 ms |
860 KB |
Output isn't correct |
| 19 |
Incorrect |
17 ms |
2676 KB |
Output isn't correct |
| 20 |
Incorrect |
18 ms |
2420 KB |
Output isn't correct |
