Submission #299389

#	Time	Username	Problem	Language	Result	Execution time	Memory
299389		Yousef_Salama	timeismoney (balkan11_timeismoney)	C++17	100 / 100	1515 ms	812 KiB

timeismoney

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

struct edge{
	int a, b, t, c;
	edge(){}
};

struct halfplane{
	long long A, B, C;
	halfplane(){}
	halfplane(long long A, long long B, long long C): A(A), B(B), C(C){}
};
struct result{
	long long t, c, a, b;
	result(long long t, long long c, long long a, long long b): t(t), c(c), a(a), b(b){}
	bool operator <(const result& r) const{
		return t * c < r.t * r.c;
	}
};

int findr(vector <int>& d, int u){
	if(d[u] == u)return u;
	else return d[u] = findr(d, d[u]);
}

vector < pair <int, int> > res;
long long mst(int n, vector <edge>& e, long long a, long long b, bool construct = false){
	vector <int> d(n);
	for(int i = 0; i < n; i++)
		d[i] = i;
	
	sort(e.begin(), e.end(), [&](const edge& x, const edge& y){
		return x.t * a + x.c * b < y.t * a + y.c * b;
	});
	
	long long cost = 0;
	for(auto[u, v, t, c] : e){
		int ur = findr(d, u), vr = findr(d, v);
		if(ur == vr)continue;
		
		if(construct)res.emplace_back(u, v);
		cost += t * a + c * b;
		d[ur] = vr;
	}
	return cost;
}
bool check(const halfplane& L, const halfplane& R, const halfplane& mid){
	return (L.A * R.B - L.B * R.A) * mid.C + (L.B * R.C - L.C * R.B) * mid.A + (L.C * R.A - L.A * R.C) * mid.B == 0;
}
result calc(int n, vector <edge>& e, const halfplane& L, const halfplane& R){
	//cout << L.A << ',' << L.B << ',' << L.C << ' ' << R.A << ',' << R.B << ',' << R.C << endl;
	halfplane mid = halfplane(L.A + R.A, L.B + R.B, mst(n, e, L.A + R.A, L.B + R.B));
	
	if(!check(L, R, mid)){
		result ret1 = calc(n, e, L, mid);
		result ret2 = calc(n, e, mid, R);
		
		if(ret1 < ret2)return ret1;
		else return ret2;
	}else{
		return result((L.C * R.B - R.C * L.B) / (L.A * R.B - R.A * L.B), (L.C * R.A - R.C * L.A) / (L.B * R.A - R.B * L.A), 
						L.A + R.A, L.B + R.B);
	}
}

int main(){
	//cout << check(halfplane(1, 1, 18), halfplane(0, 1, 11), halfplane(1, 2, 29)) << endl;
	int n, m;
	scanf("%d %d", &n, &m);
	
	vector <edge> e(m);
	for(int i = 0; i < m; i++)
		scanf("%d %d %d %d", &e[i].a, &e[i].b, &e[i].t, &e[i].c);
	
	result ret = calc(n, e, halfplane(1, 0, mst(n, e, 1, 0)), halfplane(0, 1, mst(n, e, 0, 1)));
	printf("%lld %lld\n", ret.t, ret.c);
	
	mst(n, e, ret.a, ret.b, true);
	for(auto[u, v] : res)
		printf("%d %d\n", u, v);
	
	return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
timeismoney.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |   scanf("%d %d %d %d", &e[i].a, &e[i].b, &e[i].t, &e[i].c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100