Submission #140238

#	Time	Username	Problem	Language	Result	Execution time	Memory
140238		HIR180	timeismoney (balkan11_timeismoney)	C++17	70 / 100	17 ms	1268 KiB

timeismoney

#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];
	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(up == mid || dw == mid) return;
	assert(up.fi < mid.fi && mid.fi < dw.fi);
	assert(up.sc > mid.sc && mid.sc > dw.sc);
	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:55:6:
  rep(i,vec.size()){
      ~~~~~~~~~~~~              
timeismoney.cpp:55: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:89:6:
  rep(i,ans.size()) printf("%d %d\n",ans[i].fi,ans[i].sc);
      ~~~~~~~~~~~~              
timeismoney.cpp:89:2: note: in expansion of macro 'rep'
  rep(i,ans.size()) printf("%d %d\n",ans[i].fi,ans[i].sc);
  ^~~
timeismoney.cpp:80: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:82: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);
                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 70 / 100