#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
#define int ll
int N, M, P[205];
vector<array<int, 5>> E;
int findSet(int v) {
if(P[v] == v) return v;
return P[v] = findSet(P[v]);
}
int unionSet(int u, int v) {
u = findSet(u), v = findSet(v);
if(u == v) return 0;
P[u] = v;
return 1;
}
pair<pair<int, int>, vector<int>> solve(vector<int> W) {
sort(E.begin(), E.end(),
[&](array<int, 5> A, array<int, 5> B) {
return W[A[4]] < W[B[4]];
});
for(int l = 0; l < N; l++) P[l] = l;
int A = 0, B = 0; vector<int> mst;
for(auto u : E) {
if(unionSet(u[0], u[1])) {
A += u[2], B += u[3];
mst.push_back(u[4]);
}
}
return {{A, B}, mst};
}
int area(pair<int, int> A, pair<int, int> B, pair<int, int> C) {
pair<int, int> U = {B.first - A.first, B.second - A.second};
pair<int, int> V = {C.first - A.first, C.second - A.second};
return U.first * V.second - U.second * V.first;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M;
for(int l = 0; l < M; l++) {
int U, V, T, C; cin >> U >> V >> T >> C;
E.push_back({U, V, T, C, l});
}
vector<int> res, W(M);
pair<int, int> ans = {1e8, 1e8};
for(int l = 0; l < M; l++)
W[E[l][4]] = E[l][2];
pair<int, int> A, B, C; vector<int> cur;
tie(A, res) = solve(W); ans = A;
for(int l = 0; l < M; l++)
W[E[l][4]] = E[l][3];
tie(B, cur) = solve(W);
if(B.first * B.second < A.first * A.second) {
ans = B; res = cur;
}
vector<array<pair<int, int>, 2>> ST;
ST.push_back({A, B});
while(!ST.empty()) {
A = ST.back()[0]; B = ST.back()[1]; ST.pop_back();
for(int l = 0; l < M; l++)
W[E[l][4]] = E[l][3] * (B.first - A.first)
- E[l][2] * (B.second - A.second);
tie(C, cur) = solve(W);
if(C.first * C.second < ans.first * ans.second) {
ans = C; res = cur;
}
if(area(A, B, C) >= 0) continue;
ST.push_back({A, C}); ST.push_back({C, B});
}
cout << ans.first << " " << ans.second << "\n";
sort(E.begin(), E.end(),
[&](array<int, 5> A, array<int, 5> B) {
return res[A[4]] < res[B[4]];
});
for(auto u : res) cout << E[u][0] << " " << E[u][1] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 8 |
Incorrect |
6 ms |
1040 KB |
Output isn't correct |
| 9 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 10 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 11 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 12 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 13 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 14 |
Incorrect |
5 ms |
368 KB |
Output isn't correct |
| 15 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 16 |
Incorrect |
71 ms |
468 KB |
Output isn't correct |
| 17 |
Incorrect |
86 ms |
476 KB |
Output isn't correct |
| 18 |
Incorrect |
74 ms |
468 KB |
Output isn't correct |
| 19 |
Incorrect |
614 ms |
1040 KB |
Output isn't correct |
| 20 |
Incorrect |
630 ms |
1040 KB |
Output isn't correct |
