#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(){
u = v = t = c = 0;
}
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){
return a.t*wx+a.c*wy < b.t*wx+b.c*wy;
}
struct UnionFind{
int par[205],ran[205];
void init(){ rep(i,205){ par[i]=i; ran[i]=0; } }
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;
if(ran[x]<ran[y]) par[x] = y;
else{
par[y] = x; if(ran[x]==ran[y]) ran[x]++;
}
}
}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(up == mid || dw == mid) 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:58:6:
rep(i,vec.size()){
~~~~~~~~~~~~
timeismoney.cpp:58: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:90:6:
rep(i,ans.size()) printf("%d %d\n",ans[i].fi,ans[i].sc);
~~~~~~~~~~~~
timeismoney.cpp:90:2: note: in expansion of macro 'rep'
rep(i,ans.size()) printf("%d %d\n",ans[i].fi,ans[i].sc);
^~~
timeismoney.cpp:81: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:83: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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 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 |
376 KB |
Output is correct |
| 8 |
Correct |
9 ms |
952 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
2 ms |
256 KB |
Output is correct |
| 11 |
Correct |
3 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
252 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
8 ms |
376 KB |
Output is correct |
| 15 |
Correct |
6 ms |
376 KB |
Output is correct |
| 16 |
Execution timed out |
2053 ms |
1244 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2054 ms |
1824 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2073 ms |
1656 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2060 ms |
1268 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2051 ms |
1268 KB |
Time limit exceeded |
