#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,m;
struct edge{
int u,v;
ll t,c;
edge(int a,int b,ll cc,ll d){
u = a; v = b; t = cc; c = d;
}
};
vector<edge>vec;
ll wx,wy;
bool cmp(const edge&a,const edge&b){
if(a.t*wx+a.c*wy != b.t*wx+b.c*wy) return a.t*wx+a.c*wy < b.t*wx+b.c*wy;
if(wx&&wy) return false;
else if(wx) return a.c < b.c;
else return a.t < b.t;
}
struct UnionFind{
int par[205];
void init(){ rep(i,205)par[i]=i; }
int find(int x){ if(x==par[x]) return x; else return par[x] = find(par[x]);}
void unite(int x,int y){
x = find(x); y = find(y); if(x==y) return;
par[x] = y;
}
}uf;
ll tt = 1e9,cc = 1e9;
vector<P>ans;
pair<ll,ll> ret(ll _wx,ll _wy){
wx = _wx; wy = _wy;
sort(vec.begin(),vec.end(),cmp);
uf.init();
ll X = 0, Y = 0;
vector<P>use;
rep(i,vec.size()){
if(uf.find(vec[i].u) != uf.find(vec[i].v)){
X += vec[i].t; Y += vec[i].c;
uf.unite(vec[i].u,vec[i].v);
use.pb(mp(vec[i].u,vec[i].v));
}
}
if(tt*cc > X*Y){
tt = X;
cc = Y;
ans = use;
}
return make_pair(X,Y);
}
void go(pair<ll,ll>up,pair<ll,ll>dw){
if(up.fi >= dw.fi) return;
if(up.sc <= dw.sc) return;
pair<ll,ll>mid = ret(up.sc-dw.sc,dw.fi-up.fi);
if((mid.sc-dw.sc)*(mid.fi-up.fi) == (mid.fi-dw.fi)*(mid.sc-up.sc)) return;
go(up,mid);
go(mid,dw);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int a,b; ll c,d; scanf("%d%d%lld%lld",&a,&b,&c,&d);
vec.pb(edge(a,b,c,d));
}
pair<ll,ll>up = ret(1,0);
pair<ll,ll>dw = ret(0,1);
go(up,dw);
printf("%lld %lld\n",tt,cc);
rep(i,ans.size()) printf("%d %d\n",ans[i].fi,ans[i].sc);
}
Compilation message
timeismoney.cpp: In function 'std::pair<long long int, long long int> ret(ll, ll)':
timeismoney.cpp:15:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,x) for(int i=0;i<x;i++)
timeismoney.cpp:56:6:
rep(i,vec.size()){
~~~~~~~~~~~~
timeismoney.cpp:56:2: note: in expansion of macro 'rep'
rep(i,vec.size()){
^~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:15:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,x) for(int i=0;i<x;i++)
timeismoney.cpp:88:6:
rep(i,ans.size()) printf("%d %d\n",ans[i].fi,ans[i].sc);
~~~~~~~~~~~~
timeismoney.cpp:88:2: note: in expansion of macro 'rep'
rep(i,ans.size()) printf("%d %d\n",ans[i].fi,ans[i].sc);
^~~
timeismoney.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
~~~~~^~~~~~~~~~~~~~
timeismoney.cpp:81:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a,b; ll c,d; scanf("%d%d%lld%lld",&a,&b,&c,&d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
3 ms |
632 KB |
Output is correct |
| 8 |
Correct |
8 ms |
952 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
256 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
256 KB |
Output is correct |
| 14 |
Correct |
9 ms |
376 KB |
Output is correct |
| 15 |
Correct |
7 ms |
376 KB |
Output is correct |
| 16 |
Correct |
102 ms |
476 KB |
Output is correct |
| 17 |
Correct |
107 ms |
504 KB |
Output is correct |
| 18 |
Correct |
101 ms |
376 KB |
Output is correct |
| 19 |
Correct |
859 ms |
952 KB |
Output is correct |
| 20 |
Correct |
872 ms |
952 KB |
Output is correct |
