# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
140282 | HIR180 | timeismoney (balkan11_timeismoney) | C++17 | 872 ms | 952 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |