#include <bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
using namespace std;
int fastexp(int b, int e, int mod){
int ans = 1;
while(e){
if(e&1) ans = (1ll*ans*b)%mod;
b = (1ll*b*b)%mod;
e >>= 1;
}
return ans;
}
const int N = 1e4+1;
const int mod = 998244353;
const ll INFLL = 1e18;
const int INF = 2e9;
struct dsu{
int n, *p;
dsu(int _n){
n = _n;
p = new int[n];
for(int i = 0; i < n; i++) p[i] = -1;
}
int find(int u){
if(p[u] < 0) return u;
else return p[u] = find(p[u]);
}
bool unite(int u, int v){
u = find(u); v = find(v);
if(u == v) return false;
p[u] += p[v];
p[v] = u;
return true;
}
};
int u[N],v[N],c[N],m[N];
int n,e,cc,cm;
pair<int,int> ans;
pair<int,int> find_mst(int coeff_c, int coeff_m, bool log){
int ind[e];
for(int i = 0; i < e; i++) ind[i] = i;
sort(ind, ind+e, [&] (int i, int j){
int gg = coeff_c*(c[i] - c[j]) - coeff_m*(m[j] - m[i]);
if(gg == 0) return c[i] > c[j];
else return gg < 0;
});
dsu DSU(n);
int cost = 0, money = 0;
for(int i = 0; i < e; i++){
int j = ind[i];
// cout << coeff_c << " " << coeff_m << " " << j << " " << u[j] << " " << v[j] << "\n";
if(DSU.unite(u[j],v[j])){
cost += c[j], money += m[j];
if(log) cout << u[j] << " " << v[j] << "\n";
}
}
return make_pair(cost,money);
}
bool operator < (pair<int,int> a, pair<int,int> b){
return (a.first*a.second < b.first * b.second);
}
void divide(int xl, int yl, int xr, int yr){
auto it = find_mst(yl-yr, xr-xl, false);
if(((it.first - xl) * (yr - it.second)) == ((xr - it.first) * (it.second - yl))) return;
if(it < ans){
ans = make_pair(it.first,it.second), cc = yl - yr, cm = xl - xr;
}
divide(xl, yl, it.first, it.second); divide(it.first, it.second, xr, yr);
}
void solve(){
cin >> n >> e;
for(int i = 0; i < e; i++) cin >> u[i] >> v[i] >> c[i] >> m[i];
auto min_x = find_mst(1,0,false);
auto min_y = find_mst(0,1,false);
if(min_x < min_y) ans = min_x, cc = 1, cm = 0;
else ans = min_y, cc = 0, cm = 1;
divide(min_x.first, min_x.second, min_y.first, min_y.second);
cout << ans.first << " " << ans.second << "\n";
find_mst(cc, cm, true);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
5 ms |
604 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 12 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 13 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 14 |
Incorrect |
5 ms |
348 KB |
Output isn't correct |
| 15 |
Incorrect |
4 ms |
604 KB |
Output isn't correct |
| 16 |
Incorrect |
91 ms |
980 KB |
Output isn't correct |
| 17 |
Incorrect |
99 ms |
960 KB |
Output isn't correct |
| 18 |
Incorrect |
88 ms |
848 KB |
Output isn't correct |
| 19 |
Incorrect |
797 ms |
1360 KB |
Output isn't correct |
| 20 |
Incorrect |
817 ms |
1360 KB |
Output isn't correct |
