Submission #140282

#TimeUsernameProblemLanguageResultExecution timeMemory
140282HIR180timeismoney (balkan11_timeismoney)C++17
100 / 100
872 ms952 KiB
#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)

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 timeMemoryGrader output
Fetching results...