#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<array<int,4>>v;
int pr[201];
int sz[201];
int n,m;
int find(int x){
if(x==pr[x])return x;
return pr[x] = find(pr[x]);
}
bool mergegroup(int a,int b){
a = find(a);
b = find(b);
if(a==b)return 0;
if(sz[a]<sz[b])swap(a,b);
pr[b] = a;
sz[a]+=sz[b];
return 1;
}
pair<int,int> solve(int x,int y){
vector<array<int,3>> lol;
for(int i = 0;i<v.size();i++){
lol.push_back({v[i][2]*x+v[i][3]*y,-v[i][2],i});
}
sort(lol.begin(),lol.end());
for(int i = 1;i<=n;i++){
pr[i] = i;
sz[i] = 1;
}
long long a = 0 , b = 0;
for(auto i:lol){
if(mergegroup(v[i[2]][0],v[i[2]][1])){
a+=v[i[2]][2];
b+=v[i[2]][3];
}
}
return {a,b};
}
void print(int x,int y){
vector<array<int,3>> lol;
for(int i = 0;i<v.size();i++){
lol.push_back({v[i][2]*x+v[i][3]*y,-v[i][2],i});
}
sort(lol.begin(),lol.end());
for(int i = 1;i<=n;i++){
pr[i] = i;
sz[i] = 1;
}
long long a = 0 , b = 0;
for(auto i:lol){
if(mergegroup(v[i[2]][0],v[i[2]][1])){
cout<<v[i[2]][0]-1<<" "<<v[i[2]][1]-1<<endl;
}
}
}
long long all = 1e18;
map<pair<int,int>,int> mp;
int nx = 0 , ny = 0;
bool ss = 0;
int cnt = 0;
void rec(pair<int,int>a,pair<int,int> b){
mp[a] = 1;
mp[b] = 1;
if(ss==0){
if(all>a.first*a.second){
all = a.first*a.second;
nx = 1 , ny = 0;
}
if(all>b.first*b.second){
all = b.first*b.second;
nx = 0 , ny = 0;
}
}
ss = 1;
int X = a.second-b.second;
int Y = a.first-b.first;
int gc = __gcd(abs(X),abs(Y));
if(gc){
X/=gc;Y/=gc;
}
X = -X;
pair<int,int> lol = solve(X,Y);
if(lol.first*lol.second<all){
all = lol.first*lol.second;
nx = X;
ny = Y;
}
if(mp[lol])return ;
else {
rec(a,lol);
rec(lol,b);
}
}
signed main(){
cin>>n>>m;
for(int i = 0;i<m;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
a++;b++;
v.push_back({a,b,c,d});
}
rec(solve(0,1),solve(1,0));
cout<<solve(nx,ny).first<<" "<<solve(nx,ny).second<<endl;
print(nx,ny);
return 0;
}
Compilation message
timeismoney.cpp: In function 'std::pair<long long int, long long int> solve(long long int, long long int)':
timeismoney.cpp:23:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i = 0;i<v.size();i++){
| ~^~~~~~~~~
timeismoney.cpp: In function 'void print(long long int, long long int)':
timeismoney.cpp:42:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i = 0;i<v.size();i++){
| ~^~~~~~~~~
timeismoney.cpp:50:15: warning: unused variable 'a' [-Wunused-variable]
50 | long long a = 0 , b = 0;
| ^
timeismoney.cpp:50:23: warning: unused variable 'b' [-Wunused-variable]
50 | long long a = 0 , b = 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 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
3 ms |
620 KB |
Output is correct |
| 8 |
Correct |
17 ms |
1376 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 10 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
5 ms |
484 KB |
Output is correct |
| 15 |
Correct |
4 ms |
348 KB |
Output is correct |
| 16 |
Correct |
91 ms |
604 KB |
Output is correct |
| 17 |
Correct |
105 ms |
604 KB |
Output is correct |
| 18 |
Correct |
93 ms |
604 KB |
Output is correct |
| 19 |
Correct |
1077 ms |
1544 KB |
Output is correct |
| 20 |
Correct |
1091 ms |
1536 KB |
Output is correct |
