Submission #446112

#	Time	Username	Problem	Language	Result	Execution time	Memory
446112		Evirir	timeismoney (balkan11_timeismoney)	C++17	100 / 100	1094 ms	2024 KiB

timeismoney

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
template<typename T>
using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;

const bool DEBUG = 0;
const int MAXN = 205;
const int MAXM = 10005;

struct DSU
{
	struct Node{ int p, sz; };
	int cc;
	vector<Node> dsu;
	DSU(int n){
		dsu.resize(n); cc=n;
		forn(i,0,n){ dsu[i]={i,1}; }
	}
	int rt(int u){ return (dsu[u].p==u) ? u : dsu[u].p=rt(dsu[u].p); }
	bool sameset(int u, int v){ return rt(u)==rt(v); }
	void merge(int u, int v)
	{
		u=rt(u); v=rt(v);
		if(u==v) return;
		if(dsu[u].sz<dsu[v].sz) swap(u,v);
		dsu[u].sz+=dsu[v].sz;
		dsu[v].p=dsu[u].p;
		cc--;
	}
};

struct Edge
{
	int u,v;
	ll x,y;
	int id;
	bool operator<(const Edge& e){ return x+y < e.x+e.y; }
};

int n,m;
vector<Edge> edges;
vector<ii> bestedges;
ii best={3e9,3e9};
ll besta,bestb;

ii solve(ll a, ll b, bool fin=false)
{
	vector<Edge> ve;
	for(Edge e: edges)
	{
		ve.pb({e.u, e.v, a*e.x, b*e.y, e.id});
	}
	sort(ve.begin(), ve.end());
	
	DSU dsu(n);
	ll sumx=0,sumy=0;
	for(Edge e: ve)
	{
		if(dsu.cc==1) break;
		int u=e.u, v=e.v;
		if(dsu.sameset(u,v)) continue;
		dsu.merge(u,v);
		sumx+=edges[e.id].x;
		sumy+=edges[e.id].y;
		if(fin) bestedges.pb({u,v});
	}
	ii res=ii(sumx, sumy);
	if(res.F*res.S < best.F*best.S)
	{
		best=res;
		besta=a;
		bestb=b;
	}
	return res;
}

bool good(ii a, ii b, ii c)
{
	return (c.S-b.S)*(b.F-a.F)>(b.S-a.S)*(c.F-b.F);
}

void rec(ii a, ii b)
{
	ii res=solve(a.S-b.S, b.F-a.F);
	if(good(a,res,b))
	{
		rec(a,res);
		rec(res,b);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>m;
	forn(i,0,m)
	{
		int u,v,x,y; cin>>u>>v>>x>>y;
		edges.pb(Edge{u,v,x,y,i});
	}
	
	ii minx=solve(1,0);
	ii miny=solve(0,1);
	
	rec(minx, miny);
	solve(besta, bestb, true);
	
	cout<<best.F<<" "<<best.S<<'\n';
	for(auto e: bestedges) cout<<e.F<<" "<<e.S<<'\n';
	
	return 0;
}

• Subtask 1: 100 / 100