Submission #39814

#	Time	Username	Problem	Language	Result	Execution time	Memory
39814		krauch	timeismoney (balkan11_timeismoney)	C++14	100 / 100	915 ms	2316 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define SIZE(x) (int)((x).size())
inline int readi(){
	int x=0,f=1;char ch;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct UnionFind {
	vector<int> data;
	void init(int n) { data.assign(n, -1); }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
};
struct edge {
	int x, y;
	int time, cost;
};
int A, B;
vector<edge> E;
bool cmp(const edge &a, const edge &b){
	return 1ll*a.time*A + 1ll*a.cost*B < 1ll*b.time*A + 1ll*b.cost*B;
}
ll cross(pii O, pii A, pii B){
    return 1ll*(A.first-O.first)*(B.second-O.second) - 1ll*(A.second-O.second)*(B.first-O.first);
}
int N, M, KEK;
vector<pii> lower_hull;
vector<pii> slopes;
vector<pii> ans;
pii bestmst;
pii mst(int a, int b, bool save) {
    ++KEK;
	assert(a>=0 && b>=0);
	A=a, B=b;
	sort(E.begin(),E.end(),cmp);
	UnionFind uf;
	uf.init(N);
	pii res = {0,0};
	for(int i=0; i<M; i++){
		if(uf.unionSet(E[i].x, E[i].y)){
			res.first += E[i].time;
			res.second += E[i].cost;
			if(save) ans.emplace_back(E[i].x, E[i].y);
		}
	}
	lower_hull.push_back(res);
	slopes.emplace_back(a,b);
	if(save) bestmst=res;
	return res;
}
void go(pii a, pii b) {
	pii p = mst(a.second-b.second,b.first-a.first,0);
	if(cross(p,a,b)==0) return;
	go(a,p); go(p,b);
}
int main() {
	N = readi();
	M = readi();
	E.resize(M);
	for(int i=0; i<M; i++){
		E[i].x = readi();
		E[i].y = readi();
		E[i].time = readi();
		E[i].cost = readi();
	}
	pii a = mst(1,0,0);
	pii b = mst(0,1,0);
	go(a, b);
	ll res = 1e18;
	for(pii p : lower_hull){
		res = min(res, p.first*p.second);
	}
	for(int i=0; i<SIZE(lower_hull); i++){
		if(lower_hull[i].first*lower_hull[i].second==res){
			mst(slopes[i].first, slopes[i].second, 1);
			break;
		}
	}
	assert(KEK <= 10000);
	printf("%lld %lld\n",bestmst.first,bestmst.second);
	for(pii p : ans){
		printf("%lld %lld\n",p.first,p.second);
	}
	return 0;
}

• Subtask 1: 100 / 100