Submission #207621

#	Time	Username	Problem	Language	Result	Execution time	Memory
207621		junodeveloper	timeismoney (balkan11_timeismoney)	C++17	100 / 100	509 ms	824 KiB

timeismoney

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
struct edge {
	int u,v;
	int v1,v2;
	ll val;
	bool operator<(const edge& b)const {
		if(val!=b.val)return val<b.val;
		if(v1!=b.v1)return v1<b.v1;
		return v2<b.v2;
	}
};
int n,m;
int par[210];
ll a1=1e6,a2=1e6;
vector<edge> e,rv;
int pn(int u){return u==par[u]?u:(par[u]=pn(par[u]));}
void us(int a,int b) {
	a=pn(a),b=pn(b);
	par[b]=a;
}
pll f(pll p) {
	for(int i=0;i<=n;i++)par[i]=i;
	for(auto& it:e)it.val=it.v1*p.fi+it.v2*p.se;
	sort(e.begin(),e.end());
	ll s1=0,s2=0;
	vector<edge> r;
	for(auto& it:e) {
		if(pn(it.u)!=pn(it.v)) {
			us(it.u,it.v);
			s1+=it.v1;
			s2+=it.v2;
			r.pb(it);
		}
	}
	if(s1*s2<a1*a2) {
		a1=s1,a2=s2;
		rv=r;
	}
	return {s1,s2};
}
int dbg;
void solve(pll p1,pll p2) {
	if(p1==p2)return;
	pll v(p1.se-p2.se,p2.fi-p1.fi);
	pll p=f(v);
	//cout<<'*'<<p1.fi<<' '<<p1.se<<' '<<p2.fi<<' '<<p2.se<<' '<<v.fi<<' '<<v.se<<' '<<p.fi<<' '<<p.se<<endl;
	//if(++dbg>100)exit(0);
	if(p==p1||p==p2)return;
	solve(p1,p);solve(p,p2);
}
int main() {
	ios::sync_with_stdio(false);cin.tie(0);
	srand(0);
	cin>>n>>m;
	//n=200,m=10000;
	for(int i=0;i<m;i++) {
		int x,y,v1,v2;
		cin>>x>>y>>v1>>v2;
		// while(1) {
		// 	x=rand()%n,y=rand()%n;
		// 	if(x!=y)break;
		// }
		// v1=rand()%255+1,v2=rand()%255+1;
		e.pb({x,y,v1,v2});
	}
	pll p1=f({1,0});
	pll p2=f({0,1});
	solve(p1,p2);
	cout<<a1<<' '<<a2<<'\n';
	for(auto& it:rv)cout<<it.u<<' '<<it.v<<'\n';
	return 0;
}

• Subtask 1: 100 / 100