Submission #712463

#	Time	Username	Problem	Language	Result	Execution time	Memory
712463		study	timeismoney (balkan11_timeismoney)	C++17	100 / 100	992 ms	1692 KiB

timeismoney

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 201, M = 10000, nbIter = 1000,inf = 1e9;

int comp[N],siz[N],t[M],c[M],x[M],y[M];
int fin1=inf,fin2=inf;
vector<pair<int,int>> res;

int getComp(int node){
	if (comp[node] != node) comp[node] = getComp(comp[node]);
	return comp[node];
}

bool merge(int a, int b){
	a = getComp(a);
	b = getComp(b);
	if (a != b){
		if (siz[a] < siz[b]) swap(a,b);
		siz[a] += siz[b];
		comp[b] = a;
		return true;
	}
	return false;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	for (int i=0; i<m; ++i){
		cin >> x[i] >> y[i] >> t[i] >> c[i];
	}
	for (int nb=0; nb<=nbIter; ++nb){
		vector<pair<int,int>> v,ans;
		for (int i=0; i<m; ++i){
			v.emplace_back(t[i]*(nbIter-nb)+c[i]*nb,i);
		}
		for (int i=0; i<n; ++i){
			comp[i] = i;
			siz[i] = 1;
		}
		sort(v.begin(),v.end());
		int sum1 = 0, sum2 = 0;
		for (auto [comp,id]:v){
			if (merge(x[id],y[id])){
				sum1 += t[id];
				sum2 += c[id];
				ans.emplace_back(x[id],y[id]);
			}
		}
		if (sum1*sum2 < fin1*fin2){
			res = ans;
			fin1 = sum1;
			fin2 = sum2;
		} 
	}
	cout << fin1 << ' ' << fin2 << '\n';
	for (auto i:res) cout << i.first << ' ' << i.second << '\n';
	return 0;
}

• Subtask 1: 100 / 100