oj.uz

Submission #61425

# Submission time Handle Problem Language Result Execution time Memory
61425 2018-07-25T23:56:16 Z IvanC timeismoney (balkan11_timeismoney) C++17
100 / 100
 386 ms 2668 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 3 ms 616 KB Output is correct
3 Correct 5 ms 616 KB Output is correct
4 Correct 5 ms 616 KB Output is correct
5 Correct 13 ms 756 KB Output is correct
6 Correct 8 ms 780 KB Output is correct
7 Correct 72 ms 804 KB Output is correct
8 Correct 371 ms 1964 KB Output is correct
9 Correct 4 ms 1964 KB Output is correct
10 Correct 3 ms 1964 KB Output is correct
11 Correct 2 ms 1964 KB Output is correct
12 Correct 4 ms 1964 KB Output is correct
13 Correct 4 ms 1964 KB Output is correct
14 Correct 13 ms 1964 KB Output is correct
15 Correct 9 ms 1964 KB Output is correct
16 Correct 51 ms 1964 KB Output is correct
17 Correct 60 ms 1964 KB Output is correct
18 Correct 54 ms 1964 KB Output is correct
19 Correct 337 ms 2360 KB Output is correct
20 Correct 386 ms 2668 KB Output is correct