Submission #61425

#	Time	Username	Problem	Language	Result	Execution time	Memory
61425		IvanC	timeismoney (balkan11_timeismoney)	C++17	100 / 100	386 ms	2668 KiB

timeismoney

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

typedef tuple<int,int,int> trinca;
typedef tuple<double,int,int,int,int> aresta;

const int MAXN = 210;
const double INF = 1e16;
const double EPS = 1e-6;

vector<trinca> grafo[MAXN];
int pai[MAXN],processado[MAXN],N,M,tem_que_exbir;

int Prim(double alpha,int minimiza_b){
	priority_queue<aresta, vector<aresta>, greater<aresta> > pq;

	int s1 = 0,s2 = 0;

	for(int i = 0;i<N;i++){
		pai[i] = -1;
		processado[i] = 0;
	}

	pq.push({0.0,0,0,0,-1});
	while(!pq.empty()){
		aresta davez = pq.top();
		pq.pop();
		int c1 = get<1>(davez),c2 = get<2>(davez);
		int v = get<3>(davez),p = get<4>(davez);
		if(processado[v]) continue;
		processado[v] = 1;
		pai[v] = p;
		s1 += c1;
		s2 += c2;
		for(trinca nxt : grafo[v]){
			int u = get<0>(nxt),l1 = get<1>(nxt),l2 = get<2>(nxt);
			if(minimiza_b) swap(l1,l2);
			if(processado[u]) continue;
			pq.push({alpha*l1 + (1.0 - alpha)*l2,l1,l2,u,v});
		}
	}

	if(minimiza_b) swap(s1,s2);
	if(tem_que_exbir) cout << s1 << " " << s2 << endl;

	return s1*s2;

}

int checa(double alpha){
	return min(Prim(alpha,0),Prim(1.0 - alpha,1));
}

int main(){

	cin >> N >> M;
	for(int i = 1;i<=M;i++){
		int u,v,w1,w2;
		cin >> u >> v >> w1 >> w2;
		grafo[u].push_back({v,w1,w2});
		grafo[v].push_back({u,w1,w2});
	}

	double ini = 0.0,fim = 1.0;
	while(fim - ini > EPS){
		double m1 = ini + (fim - ini)/3.0;
		double m2 = fim - (fim - ini)/3.0;
		if(checa(m1) < checa(m2)){
			fim = m2 - EPS;
		}
		else{
			ini = m1 + EPS;
		}
	}

	if(Prim(ini,0) < Prim(1.0 - ini,1)){
		tem_que_exbir = 1;
		Prim(ini,0);
		for(int i = 1;i<N;i++) cout << i << " " << pai[i] << endl; 
	}
	else{
		tem_que_exbir = 1;
		Prim(1.0 - ini,1);
		for(int i = 1;i<N;i++) cout << i << " " << pai[i] << endl; 
	}

	return 0;
}

• Subtask 1: 100 / 100