Submission #106850

#	Time	Username	Problem	Language	Result	Execution time	Memory
106850		ami	timeismoney (balkan11_timeismoney)	C++17	100 / 100	358 ms	1088 KiB

timeismoney

#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using ll = long long;

template<int N>
struct disjoint_sets {
	int r[N];
	disjoint_sets() {
		memset(r,~0,sizeof(r));
	}
	void reset(int n) {
		rep(i,0,n) r[i]=-1;
	}
	int get(int x) {
		return r[x]<0 ? x : r[x]=get(r[x]);
	}
	int size(int x) {
		return -r[get(x)];
	}
	bool join(int x,int y) {
		x=get(x);
		y=get(y);
		if (x==y) return false;
		if (r[x]>r[y]) swap(x,y);
		r[x]+=r[y];
		r[y]=x;
		return true;
	}
};

struct edge_t {
	int x,y,t,c;
	ll w;
};

ll const INF=ll(1e18);
int const MAXN=220;
int const MAXM=11000;
int N,M;
vector<edge_t> E;
disjoint_sets<MAXN> DS;
vector<pair<int,int>> res;

pair<ll,ll> test(ll x,ll y,bool out=false) {
	for (auto &e:E) {
		e.w=e.t*x + e.c*y;
	}
	
	sort(E.begin(),E.end(),[](const edge_t &a, const edge_t &b) {
		return a.w < b.w;
	});
	
	DS.reset(N);
	
	int cc=N;
	ll st=0,sc=0;
	for (auto e:E) if (DS.join(e.x,e.y)) {
		st+=e.t;
		sc+=e.c;
		if (out) res.emplace_back(e.x,e.y);
		cc--;
		if (cc==1) break;
	}
	
	return {st,sc};
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	cin>>N>>M;
	rep(i,0,M) {
		int x,y,t,c;
		cin>>x>>y>>t>>c;
		E.push_back({x,y,t,c,0});
	}
	
	int const MAXX=1000;
	ll best=INF;
	int bestx=-1;
	rep(x,0,MAXX+1) {
		ll st,sc;
		tie(st,sc)=test(x,MAXX-x);
		if (best>st*sc) {
			best=st*sc;
			bestx=x;
		}
	}
	
	ll st,sc;
	tie(st,sc)=test(bestx,MAXX-bestx,true);
	
	cout<<st<<" "<<sc<<"\n";
	for (auto p:res) cout<<p.first<<" "<<p.second<<"\n";
}

• Subtask 1: 100 / 100