Submission #637885

#	Time	Username	Problem	Language	Result	Execution time	Memory
637885		google	timeismoney (balkan11_timeismoney)	C++17	70 / 100	2082 ms	596 KiB

timeismoney

#include<bits/stdc++.h>
using namespace std;
const int siz = 205;
int p[siz],sz[siz];
int findp(int a){
	if (p[a] == a) return a;
	return p[a] = findp(p[a]);
}
void unite(int a, int b){
	if (sz[a] < sz[b]) swap(a,b);
	p[b] = a;
	sz[a] += sz[b];
}
int gcd(int a, int b){
	if (a < b) swap(a,b);
	return b?gcd(b,a%b):a;
}
int I,J;
bool cmp(pair<pair<int,int>,pair<int,int>> & a, pair<pair<int,int>,pair<int,int>> &b){
	return a.second.first*I+a.second.second*J < b.second.first*I+b.second.second*J;
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n,m; cin >> n >> m;
	vector<pair<pair<int,int>,pair<int,int>>> v(m);
	pair<pair<int,int>,vector<pair<int,int>>> ans;
	for (int i = 0;i<m;i++) cin >> v[i].first.first >> v[i].first.second >> v[i].second.first >> v[i].second.second;
	long long best = LLONG_MAX;
	for (I = 1;I<255;I++){
		for (J = 1;J<255;J++){
			if (I != 1 && J != 1 && gcd(I,J) == 1) continue;
			for (int i = 0;i<n;i++) {p[i] = i;sz[i] = 1;}
			sort(v.begin(),v.end(),cmp);
			int cnt1 = 0,cnt2 = 0;
			vector<pair<int,int>> e;
			for (int i = 0;i<m;i++){
				auto [a,b] = v[i].first;
				a = findp(a);
				b = findp(b);
				if (a == b) continue;
				e.push_back(v[i].first);
				unite(a,b);
				cnt1 += v[i].second.first;
				cnt2 += v[i].second.second;
			}
			if (1LL*cnt1*cnt2 < best){
				best = 1LL*cnt1*cnt2;
				ans.first.first = cnt1;
				ans.first.second = cnt2;
				ans.second.clear();
				for (auto &a:e) ans.second.push_back(a);
			}
		}
	}
	cout << ans.first.first << ' ' << ans.first.second << '\n';
	for (auto [a,b]:ans.second) cout << a << ' ' << b << '\n';
	return 0;
}

• Subtask 1: 70 / 100