Submission #969853

#	Time	Username	Problem	Language	Result	Execution time	Memory
969853		happy_node	timeismoney (balkan11_timeismoney)	C++17	100 / 100	335 ms	1452 KiB

timeismoney

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

typedef long long ll;

const int MX=205;
int N,M;
vector<array<int,3>> adj[MX];

ll w[10005];
array<ll,4> e[10005];

struct DSU {
	int par[MX];

	int find(int v) {
		return par[v]==v?v:par[v]=find(par[v]);
	}

	bool merge(int u, int v) {
		u=find(u), v=find(v);
		if(u==v) return false;
		par[u]=v;
		return true;
	}

	void prep() {
		for(int i=0;i<MX;i++) par[i]=i;
	}
} ds;

#define pt pair<ll,ll>
#define px first
#define py second

ll optV=0, optT=0, optC=0;
vector<pair<ll,ll>> optE, cur;

ll area(pt a, pt b, pt c) {
	return (b.px-a.px)*(c.py-b.py)-(c.px-b.px)*(b.py-a.py);
}

vector<int> ord;

pt kruskal() {
	cur.clear();
	sort(ord.begin(),ord.end(),[&](int i, int j){
		return w[i]<w[j];
	});

	ll st=0, sc=0;
	ds.prep();
	
	for(auto x:ord) {
		auto [u,v,t,c]=e[x];
		if(ds.merge(u,v)) {
			cur.push_back({u,v});
			st+=t;
			sc+=c;
		}
	}

	return {st,sc};
}

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

	cin>>N>>M;

	for(int i=0;i<M;i++) {
		int x,y,t,c;
		cin>>x>>y>>t>>c;
		adj[x].push_back({y,t,c});
		adj[y].push_back({x,t,c});
		e[i]={x,y,t,c};
	}

	for(int i=0;i<M;i++) ord.push_back(i);

	// time on x axis cost on y axis

	// get point A -> minimize x axis 
	for(int i=0;i<M;i++) 
		w[i]=e[i][2];

	pt A=kruskal();

	optV=A.px*A.py;
	optT=A.px;
	optC=A.py;
	optE=cur;

	// get point B -> minimize y axis
	for(int i=0;i<M;i++)
		w[i]=e[i][3];

	pt B=kruskal();

	if(B.px*B.py<optV) {
		optV=B.px*B.py;
		optT=B.px;
		optC=B.py;
		optE=cur;
	}

	vector<pair<pt,pt>> stk;
	stk.push_back({A,B});

	while(!stk.empty()) {
		auto [A,B]=stk.back(); stk.pop_back();

		// assing new weight based on Py(Bx - Ax) + Px(Ay - By)
		// y axis is cost, x axis is time

		for(int i=0;i<M;i++) 
			w[i]=e[i][3]*(B.px-A.px) + e[i][2]*(A.py-B.py);
		
		pt P=kruskal();

		// isn't on the lower convex hull
		if(area(A,B,P)>=0) continue;

		if(P.px*P.py<optV) {
			optV=P.px*P.py;
			optT=P.px;
			optC=P.py;
			optE=cur;
		}

		stk.push_back({A,P});
		stk.push_back({P,B});
	}

	cout<<optT<<" "<<optC<<'\n';
	for(auto [u,v]:optE) {
		cout<<u<<" "<<v<<'\n';
	}
}

• Subtask 1: 100 / 100