#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair < ll, ll >
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
struct Edge {
ll a, b, t, m;
};
const ll N = 2e2+10, M = 1e4+10;
ll n, m;
Edge edges[M];
ll x, y;
ll par[N];
int fn( int i ) {
if(par[i] == i) return i;
return par[i] = fn(par[i]);
}
void un( int a, int b ) {
a = fn(a); b = fn(b);
if(a != b) par[b] = a;
return;
}
void res( void ) {
for(ll i = 0; i < n; i++) {
par[i] = i;
}
}
bool check_un( int a, int b ) {
return (fn(a) == fn(b));
}
pair < vector < Edge >, pii > mst() {
ll tout = 0;
ll mout = 0;
vector < Edge > edgout;
res();
for(ll i = 0; i < m; i++) {
if(!check_un(edges[i].a, edges[i].b)) {
un(edges[i].a, edges[i].b);
tout += edges[i].t;
mout += edges[i].m;
edgout.pb(edges[i]);
}
}
return mp(edgout, mp(tout, mout));
}
bool s_func_t( Edge a, Edge b ) {
if(b.t > a.t) return 1;
if(b.t < a.t) return 0;
if(b.m > a.m) return 1;
return 0;
}
bool s_func_m( Edge a, Edge b ) {
if(b.m > a.m) return 1;
if(b.m < a.m) return 0;
if(b.t > a.t) return 1;
return 0;
}
bool s_func_xy( Edge a, Edge b ) {
return ((b.t * x) + (b.m * y) > (a.t * x) + (a.m * y)) ? 1 : 0;
}
pair < vector < Edge >, pii > daq( pair < vector < Edge >, pii >& a, pair < vector < Edge >, pii >& b ) {
y = b.S.F - a.S.F;
x = a.S.S - b.S.S;
sort(edges, edges + m, s_func_xy);
pair < vector < Edge >, pii > out = mst();
if(out.S == a.S || out.S == b.S) {
if(a.S.F * a.S.S < b.S.F * b.S.S) return a;
else return b;
}
pair < vector < Edge >, pii > temp1 = daq(a, out);
pair < vector < Edge >, pii > temp2 = daq(out, b);
if(temp1.S.F * temp1.S.S < out.S.F * out.S.S) out = temp1;
if(temp2.S.F * temp2.S.S < out.S.F * out.S.S) out = temp2;
return out;
}
int main( void ) {
FIO
cin >> n >> m;
for(int i = 0; i < m; i++) {
cin >> edges[i].a >> edges[i].b >> edges[i].t >> edges[i].m;
}
sort(edges, edges + m, s_func_t);
pair < vector < Edge >, pii > temp1 = mst();
sort(edges, edges + m, s_func_m);
pair < vector < Edge >, pii > temp2 = mst();
pair < vector < Edge >, pii > sol = daq(temp1, temp2);
cout << sol.S.F << " " << sol.S.S << "\n";
for(int i = 0; i < (int) sol.F.size(); i++) {
cout << sol.F[i].a << " " << sol.F[i].b << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
113 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
306 ms |
65536 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
159 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
922 ms |
65536 KB |
Execution killed with signal 9 |
| 8 |
Execution timed out |
2070 ms |
25688 KB |
Time limit exceeded |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
6 ms |
348 KB |
Output is correct |
| 15 |
Correct |
4 ms |
588 KB |
Output is correct |
| 16 |
Runtime error |
1761 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
1797 ms |
65536 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
1139 ms |
65536 KB |
Execution killed with signal 9 |
| 19 |
Execution timed out |
2043 ms |
14204 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2080 ms |
19308 KB |
Time limit exceeded |
