Submission #889489

#	Time	Username	Problem	Language	Result	Execution time	Memory
889489		WonderfulWhale	timeismoney (balkan11_timeismoney)	C++17	100 / 100	994 ms	2188 KiB

timeismoney

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

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

ostream& operator<<(ostream& os, pii x) {
	os << "{" << x.st << ", " << x.nd << "}";
	return os;
}

int n, m;
vector<pair<pii, pii>> edges;

int p[209];
int Find(int x) {
	return x==p[x]?x:p[x]=Find(p[x]);
}
void Union(int a, int b) {
	p[Find(a)] = Find(b);
}
pii ans;
vector<pii> res;
void mst(int a, int b) {
	iota(p, p+n, 0);
	res.clear();
	ans = {0, 0};
	vector<pair<int, pair<pii, pii>>> v;
	for(auto [x, y]:edges) {
		v.pb({a*y.st+b*y.nd, {x, y}});
	}
	sort(all(v));
	for(auto [x, y]:v) {
		if(Find(y.st.st)!=Find(y.st.nd)) {
			res.pb(y.st);
			ans.st+=y.nd.st;
			ans.nd+=y.nd.nd;
			Union(y.st.st, y.st.nd);
		}
	}
}

pii f(pii a, pii b) {
	int x = b.st-a.st;
	int y = b.nd-a.nd;
	mst(-y, x);
	int x1 = ans.st-a.st;
	int y1 = ans.nd-a.nd;
	pii ret;
	if(a.st*a.nd<b.st*b.nd) {
		ret = a;
	} else {
		ret = b;
	}
	pii mid = ans;
	if(x*y1-x1*y<0) {
		pii r1 = f(a, mid);
		pii r2 = f(mid, b);
		if(r1.st*r1.nd<ret.st*ret.nd) ret = r1;
		if(r2.st*r2.nd<ret.st*ret.nd) ret = r2;
	}
	return ret;
}

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

	cin >> n >> m;
	for(int i=0;i<m;i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		edges.pb({{a, b}, {c, d}});
	}
	int CNST = 1000000;
	mst(CNST, 1);
	pii p1 = ans;
	mst(1, CNST);
	pii p2 = ans;
	pii ret = f(p1, p2);
	mst(ret.nd, ret.st);
	cout << ans.st << " " << ans.nd << "\n";
	for(pii x:res) cout << x.st << " " << x.nd << "\n";
}

• Subtask 1: 100 / 100