Submission #648372

#	Time	Username	Problem	Language	Result	Execution time	Memory
648372		inksamurai	timeismoney (balkan11_timeismoney)	C++17	100 / 100	1394 ms	724 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3Rz7lEu ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

struct dsu{
	int _n;
	vi si,par,leb;
	dsu(int n=0){
		init(n);
	}
	void init(int n=0){
		_n=n;
		par=vi(_n,0);
		si=vi(_n,0);
		leb=vi(_n,-1);
		rep(i,n){
			si[i]=1;
			par[i]=i;
		}	
	}
	int parent(int u){return par[u]=(par[u]==u?u:parent(par[u]));}
	bool same(int u,int v){return parent(u)==parent(v);}
	void merge(int u,int v){
		u=parent(u),v=parent(v);
		if(!same(u,v)){
			if(si[u]<si[v]) swap(u,v);
			leb[u]=max(leb[u],leb[v]);
			_n-=1;
			si[u]+=si[v];
			par[v]=u;
		}
	}
	int size(int v=-1){return v==-1?_n:si[parent(v)];}
};

ll ccw(pii a,pii b,pii c){
	return a.fi*(b.se-c.se)+b.fi*(c.se-a.se)+c.fi*(a.se-b.se);
}

int cofx,cofy;

struct E{
	int u,v,w,z;
	E(int _u=0,int _v=0,int _w=0,int _z=0):u(_u),v(_v),w(_w),z(_z){}
	bool operator<(const E&a)const{
		return z*cofx-w*cofy<a.z*cofx-a.w*cofy;
	}
};

signed main(){
_3Rz7lEu;
	int n,m;
	cin>>n>>m;
	vec(E) es;
	rep(i,m){
		int u,v,w,z;
		cin>>u>>v>>w>>z;
		es.pb(E(u,v,w,z));
	}
	dsu uf(n);
	vec(pii) pns;
	auto mst=[&](int x,int y,int t=0)->pii{
		rep(i,n){
			uf.par[i]=i;
			uf.si[i]=1;
		}
		cofx=x,cofy=y;
		sort(es.begin(),es.end());
		pii p={0,0};
		for(auto e:es){
			int u=e.u,v=e.v,w=e.w,z=e.z;
			if(uf.same(u,v)) continue;
			uf.merge(u,v);
			p.fi+=w;
			p.se+=z;
			if(t){
				pns.pb({u,v});
			}
		}
		return p;
	};
	ll mi=1e18;
	int dx=-1,dy=-1;
	auto add=[&](int x,int y,ll val)->void{
		if(val<mi){
			mi=val;
			dx=x,dy=y;
		}
	};
	auto dnc=[&](auto&self,pii l,pii r)->void{
		int x=r.fi-l.fi,y=r.se-l.se;
		pii p=mst(x,y);
		if(ccw(l,p,r)<=0) return;
		add(x,y,1ll*p.fi*p.se);
		self(self,l,p);
		self(self,p,r);
	};
	pii l=mst(-1,0);
	add(1,0,l.fi*l.se);
	pii r=mst(0,1);
	add(0,1,r.fi*r.se);
	dnc(dnc,l,r);
	pii p=mst(dx,dy,1);
	cout<<p.fi<<" "<<p.se<<"\n";
	for(auto p:pns){
		cout<<p.fi<<" "<<p.se<<"\n";
	}
}

• Subtask 1: 100 / 100