Submission #1009334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009334		vjudge1	timeismoney (balkan11_timeismoney)	C++17	75 / 100	2063 ms	672 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]]});
		}
	}
}

void rek (int t1, int m1, int t2, int m2, double proslik1, double proslik2){
	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)){
		k1 = 1, k2 = -proslik1;
		mst();
		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});
			}
		}
		k1 = 1, k2 = -proslik2;
		mst();
		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});
			}
		}
		return;
	}
	rek(t1, m1, t_novi, m_novi, proslik1, k);
	rek(t_novi, m_novi, t2, m2, k, proslik2);
}

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;
	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});
			}
		}
	mst();
	int t2 = t_novi;
	int m2 = m_novi;
	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});
			}
		}
	//cout << t1 << " " << m1 << "  " << t2 << " " << m2 << endl;
	rek(t1, m1, t2, m2, 1, 1);
	//cout << ans << "\n";
	cout << anst << " " << ansm << endl;
	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 rek(int, int, int, int, double, double)':
timeismoney.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    for (int i = 0; i < tr.size(); i++){
      |                    ~~^~~~~~~~~~~
timeismoney.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |    for (int i = 0; i < tr.size(); i++){
      |                    ~~^~~~~~~~~~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |    for (int i = 0; i < tr.size(); i++){
      |                    ~~^~~~~~~~~~~
timeismoney.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |    for (int i = 0; i < tr.size(); i++){
      |                    ~~^~~~~~~~~~~
timeismoney.cpp:136: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]
  136 |  for (int i = 0; i < ans2.size(); i++){
      |                  ~~^~~~~~~~~~~~~

• Subtask 1: 75 / 100