Submission #1061889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061889		nishkarsh	timeismoney (balkan11_timeismoney)	C++14	50 / 100	817 ms	1360 KiB

timeismoney

#include <bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
using namespace std;

int fastexp(int b, int e, int mod){
	int ans = 1;
	while(e){
		if(e&1) ans = (1ll*ans*b)%mod;
		b = (1ll*b*b)%mod;
		e >>= 1;
	}
	return ans;
}

const int N = 1e4+1;
const int mod = 998244353;
const ll INFLL = 1e18;
const int INF = 2e9;

struct dsu{
	int n, *p;
	dsu(int _n){
		n = _n;
		p = new int[n];
		for(int i = 0; i < n; i++) p[i] = -1;
	}
	int find(int u){
		if(p[u] < 0) return u;
		else return p[u] = find(p[u]);
	}
	bool unite(int u, int v){
		u = find(u); v = find(v);
		if(u == v) return false;
		p[u] += p[v];
		p[v] = u;
		return true;
	}
};

int u[N],v[N],c[N],m[N];
int n,e,cc,cm;
pair<int,int> ans;

pair<int,int> find_mst(int coeff_c, int coeff_m, bool log){
	int ind[e];
	for(int i = 0; i < e; i++) ind[i] = i;
	sort(ind, ind+e, [&] (int i, int j){
		int gg = coeff_c*(c[i] - c[j]) - coeff_m*(m[j] - m[i]);
		if(gg == 0) return c[i] > c[j];
		else return gg < 0;
	});

	dsu DSU(n);

	int cost = 0, money = 0;

	for(int i = 0; i < e; i++){
		int j = ind[i];
		// cout << coeff_c << " " << coeff_m << " " << j << " " << u[j] << " " << v[j] << "\n";
		if(DSU.unite(u[j],v[j])){
			cost += c[j], money += m[j];
			if(log) cout << u[j] << " " << v[j] << "\n";
		}
	}
	return make_pair(cost,money);
}

bool operator < (pair<int,int> a, pair<int,int> b){
	return (a.first*a.second < b.first * b.second);
}

void divide(int xl, int yl, int xr, int yr){
	auto it = find_mst(yl-yr, xr-xl, false);
	if(((it.first - xl) * (yr - it.second)) == ((xr - it.first) * (it.second - yl))) return;

	if(it < ans){
		ans = make_pair(it.first,it.second), cc = yl - yr, cm = xl - xr;
	}
	divide(xl, yl, it.first, it.second); divide(it.first, it.second, xr, yr);
}

void solve(){
	cin >> n >> e;
	for(int i = 0; i < e; i++) cin >> u[i] >> v[i] >> c[i] >> m[i];

	auto min_x = find_mst(1,0,false);
	auto min_y = find_mst(0,1,false);

	if(min_x < min_y) ans = min_x, cc = 1, cm = 0;
	else ans = min_y, cc = 0, cm = 1;

	divide(min_x.first, min_x.second, min_y.first, min_y.second);

	cout << ans.first << " " << ans.second << "\n";
	find_mst(cc, cm, true);

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t = 1;
	// cin >> t;
	while(t--){
		solve();
	}

	return 0;
}

• Subtask 1: 50 / 100