#include <bits/stdc++.h>
using namespace std;
function<bool(tuple<int,int,int,int>,tuple<int,int,int,int>)> get_comp(int a, int b){
return [a, b](tuple<int,int,int,int> x, tuple<int,int,int,int> y){
return a*get<2>(x) + b*get<3>(x) < a*get<2>(y) + b*get<3>(y);
};
}
int n, m;
vector<tuple<int,int,int,int> > edges;
class DSU{
private:
int p[256];
public:
DSU(){
memset(p, -1, sizeof(p));
}
int f(int u){
if(p[u] == -1) return u;
else return p[u] = f(p[u]);
}
bool u(int x, int y){
x = f(x); y = f(y);
if(x == y) return false;
p[x] = y;
return true;
}
};
tuple<int,int,int,int> compute_value(int a, int b){
// Careful! This function takes O(M log M + N)
sort(edges.begin(), edges.end(), get_comp(a,b));
DSU d;
int st = 0, sc = 0;
for(auto e : edges){
int x, y, t, c; tie(x, y, t, c) = e;
if(d.u(x, y)){
st += t;
sc += c;
}
}
return make_tuple(st, sc, a, b);
}
tuple<int,int,int,int> track_min(tuple<int,int,int,int> x, tuple<int,int,int,int> y){
if(1ll*get<0>(x)*get<1>(x) > 1ll*get<0>(y)*get<1>(y)) return y;
else return x;
}
tuple<int,int,int,int> search(int a1, int b1, int a2, int b2){
auto lv = compute_value(a1, b1);
auto rv = compute_value(a2, b2);
int am = get<1>(rv) - get<1>(lv);
int bm = get<0>(rv) - get<0>(lv);
auto ret = track_min(lv, rv);
auto mv = compute_value(am, bm);
ret = track_min(ret, mv);
if(1ll * get<0>(ret) * get<1>(ret) != 1ll * get<0>(mv) * get<1>(mv)){
ret = track_min(ret, search(a1, b1, am, bm));
ret = track_min(ret, search(am, bm, a2, b2));
}
return ret;
}
int main(){
scanf("%d%d",&n,&m);
int x, y, t, c;
for(int i = 0; i < m; i++){
scanf("%d%d%d%d",&x,&y,&t,&c);
edges.emplace_back(x,y,t,c);
}
auto ans = search(1, 0, 0, 1);
sort(edges.begin(), edges.end(), get_comp(get<2>(ans), get<3>(ans)));
DSU d;
int st = 0, sc = 0;
vector<pair<int,int> > ansvec;
for(auto e : edges){
tie(x, y, t, c) = e;
if(d.u(x, y)){
st += t;
sc += c;
ansvec.emplace_back(x, y);
}
}
printf("%d %d\n", st, sc);
for(auto p : ansvec){
printf("%d %d\n", p.first, p.second);
}
return 0;
}
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
timeismoney.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d%d%d%d",&x,&y,&t,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Execution timed out |
2072 ms |
49752 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2075 ms |
34984 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2078 ms |
11268 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2092 ms |
1896 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2093 ms |
2340 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2097 ms |
532 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2095 ms |
588 KB |
Time limit exceeded |
| 9 |
Runtime error |
1722 ms |
65540 KB |
Execution killed with signal 9 |
| 10 |
Execution timed out |
2072 ms |
33072 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2097 ms |
56280 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2079 ms |
17940 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2074 ms |
18100 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2087 ms |
2560 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2084 ms |
3632 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2081 ms |
672 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2081 ms |
648 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2082 ms |
888 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2079 ms |
852 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2082 ms |
708 KB |
Time limit exceeded |
