#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double Lf;
typedef pair<int, int> pii;
const int maxn = 255;
const int maxm = 10005;
int n, m;
int vis[maxm];
class Point{
public:
int x, y;
Point(){}
Point(int x_, int y_): x(x_), y(y_){}
inline bool operator == (const Point &oth)const{ return (x == oth.x && y == oth.y); }
inline int operator * (const Point &oth)const{ return x * oth.x + y * oth.y; }
inline Point operator * (const int &oth)const{ return Point(x * oth, y * oth); }
inline Point& operator += (const Point &oth){ x += oth.x, y += oth.y; return *this; }
inline Point& operator -= (const Point &oth){ x -= oth.x, y -= oth.y; return *this; }
inline Point operator - (const Point &oth)const{ Point ret = *this; ret -= oth; return ret; }
};
class Edge{
public:
int u, v;
Point val;
Edge(){}
Edge(int u_, int v_, Point val_): u(u_), v(v_), val(val_){}
} ed[maxm];
class Dsu{
private:
inline int find(int x){ return (x == fa[x]) ? x : (fa[x] = find(fa[x])); }
public:
int fa[maxn];
inline void init(){ FOR(i, 0, n) fa[i] = i; return; }
inline bool merge(int x, int y){
x = find(x), y = find(y);
if(x == y)
return false;
fa[x] = y;
return true;
}
} dsu;
inline Point kruscal(Point w){
vector<pii> vec;
FOR(i, 0, m)
vec.PB(MP(w * ed[i].val, i));
sort(vec.begin(), vec.end());
dsu.init();
Point ret(0, 0);
memset(vis, 0, sizeof(vis));
FOR(i, 0, vec.size()){
int id = vec[i].snd;
ret += ed[id].val * (vis[id] = dsu.merge(ed[id].u, ed[id].v));
}
return ret;
}
inline Point solve(Point A, Point B){
// printf("A = (%d %d) B = (%d %d)\n", A.x, A.y, B.x, B.y);
Point W = A - B; swap(W.x, W.y); W.x = -W.x;
Point C = kruscal(W);
Point P = ((C == A || C == B) ? A : solve(A, C)), Q = ((C == A || C == B) ? B : solve(C, B));
return (1ll * P.x * P.y < 1ll * Q.x * Q.y ? P : Q);
}
int main(){
scanf("%d%d", &n, &m);
FOR(i, 0, m){
int u, v, t, c; scanf("%d%d%d%d", &u, &v, &t, &c);
ed[i] = Edge(u, v, Point(t, c));
}
Point A = kruscal(Point(0, 1));
Point B = kruscal(Point(1, 0));
Point C = solve(A, B);
kruscal(Point(C.y, C.x));
printf("%d %d\n", C.x, C.y);
FOR(i, 0, m) if(vis[i])
printf("%d %d\n", ed[i].u, ed[i].v);
return 0;
}
Compilation message
timeismoney.cpp: In function 'Point kruscal(Point)':
timeismoney.cpp:5:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define FOR(i, x, y) for(int i = (x); i < (y); ++i)
| ^
timeismoney.cpp:68:2: note: in expansion of macro 'FOR'
68 | FOR(i, 0, vec.size()){
| ^~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
timeismoney.cpp:86:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
86 | int u, v, t, c; scanf("%d%d%d%d", &u, &v, &t, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
376 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
2 ms |
364 KB |
Output is correct |
| 8 |
Correct |
9 ms |
764 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
7 ms |
364 KB |
Output is correct |
| 15 |
Correct |
5 ms |
364 KB |
Output is correct |
| 16 |
Correct |
107 ms |
364 KB |
Output is correct |
| 17 |
Correct |
109 ms |
364 KB |
Output is correct |
| 18 |
Correct |
105 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1000 ms |
764 KB |
Output is correct |
| 20 |
Correct |
1012 ms |
800 KB |
Output is correct |
