Submission #1009347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009347		vjudge1	timeismoney (balkan11_timeismoney)	C++17	40 / 100	2087 ms	604 KiB

timeismoney

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

const int maxm = 100005, maxn = 205;
int n, m;
int x[maxm], y[maxm], t[maxm], c[maxm];
int in[maxm];
int parent[maxn], vel[maxn];
long long ans = 1e18, anst, ansm;
long long t_novi, m_novi;
double k1, k2;
vector <pair <int, int> > ans2, tr;

int comp (int a, int b){
	if (k1 * t[a] + k2 * c[a] < k1 * t[b] + k2 * c[b]){
		return 1;
	}
	return 0;
}

int find (int a){
	if (parent[a] == a){
		return a;
	}
	return parent[a] = find(parent[a]);
}

void unite (int p1, int p2){
	if (vel[p1] > vel[p2]){
		swap(p1, p2);
	}
	parent[p1] = p2;
	vel[p2] += vel[p1];
	vel[p1] = 0;
}

void mst (){
	tr.clear();
	for (int i = 0; i < m; i++){
		in[i] = i;
	}
	sort(in, in + m, comp);
	for (int i = 0; i < n; i++){
		vel[i] = 1, parent[i] = i;
	}
	/*
	for (int i = 0; i < m; i++){
		cout << x[in[i]] << " " << y[in[i]] << " " << t[in[i]] << endl;
	}
	cout << endl;*/
	t_novi = 0, m_novi = 0;
	for (int i = 0; i < m; i++){
		int p1 = find(x[in[i]]);
		int p2 = find(y[in[i]]);
		if (p1 != p2){
			unite(p1, p2);
			t_novi += t[in[i]];
			m_novi += c[in[i]];
			tr.push_back({x[in[i]], y[in[i]]});
		}
	}
	
	if (t_novi * m_novi < ans){
		ans = t_novi * m_novi;
		anst = t_novi;
		ansm = m_novi;
		ans2.clear();
		for (int i = 0; i < tr.size(); i++){
			ans2.push_back({tr[i].first, tr[i].second});
		}
	}
}

void rek (int t1, int m1, int t2, int m2){
	double tt1 = t1, tt2 = t2, mm1 = m1, mm2 = m2;
	//cout << t1 << " " << m1 << " " << t2 << " " << m2 << endl;
	double k = (tt1 - tt2) / (mm1 - mm2);
	//cout << k << endl;
	k1 = 1, k2 = -k;
	mst();
	//cout << t_novi << " " << m_novi << endl;
	if ((t_novi == t1 and m_novi == m1) or (t_novi == t2 and m_novi == m2)){
		return;
	}
	rek(t1, m1, t_novi, m_novi);
	rek(t_novi, m_novi, t2, m2);
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		cin >> x[i] >> y[i] >> t[i] >> c[i];
	}
	k1 = 1, k2 = 0;
	mst();
	int t1 = t_novi;
	int m1 = m_novi;
	k1 = 0, k2 = 1;
	mst();
	int t2 = t_novi;
	int m2 = m_novi;
	//cout << t1 << " " << m1 << "  " << t2 << " " << m2 << endl;
	rek(t1, m1, t2, m2);
	//cout << ans << "\n";
	cout << anst << " " << ansm << "\n";
	for (int i = 0; i < ans2.size(); i++){
		cout << ans2[i].first << " " << ans2[i].second << "\n";
	}
	
	return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'void mst()':
timeismoney.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int i = 0; i < tr.size(); i++){
      |                   ~~^~~~~~~~~~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:110:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |  for (int i = 0; i < ans2.size(); i++){
      |                  ~~^~~~~~~~~~~~~

• Subtask 1: 40 / 100