oj.uz

Submission #61701

# Submission time Handle Problem Language Result Execution time Memory
61701 2018-07-26T11:11:52 Z IvanC timeismoney (balkan11_timeismoney) C++17
100 / 100
 444 ms 2272 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

vector<trinca> grafo[MAXN];
int processado[MAXN],N,M,tem_que_exbir;
int matA[MAXN][MAXN],matB[MAXN][MAXN];
vector<quadra> pares;

int Prim(double alpha,int minimiza_b){

	pares.clear();
	priority_queue<aresta, vector<aresta>, greater<aresta> > pq;

	int s1 = 0,s2 = 0;

	for(int i = 0;i<N;i++){
		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;
		s1 += c1;
		s2 += c2;
		if(p != -1) pares.push_back({min(p,v),max(p,v),c1,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});
		}
	}

	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)){
		Prim(ini,0);
		int s1 = 0,s2 = 0;
		sort(pares.begin(),pares.end());
		for(quadra davez : pares){
			s1 += get<2>(davez);
			s2 += get<3>(davez);
		}
		printf("%d %d\n",s1,s2);
		for(quadra davez : pares){
			printf("%d %d\n",get<0>(davez),get<1>(davez));
		}
	}
	else{
		Prim(1.0 - ini,1);
		int s1 = 0,s2 = 0;
		sort(pares.begin(),pares.end());
		for(quadra davez : pares){
			s2 += get<2>(davez);
			s1 += get<3>(davez);
		}
		printf("%d %d\n",s1,s2);
		for(quadra davez : pares){
			printf("%d %d\n",get<0>(davez),get<1>(davez));
		} 
	}

	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 4 ms 400 KB Output is correct
4 Correct 4 ms 608 KB Output is correct
5 Correct 9 ms 608 KB Output is correct
6 Correct 8 ms 744 KB Output is correct
7 Correct 58 ms 772 KB Output is correct
8 Correct 444 ms 1956 KB Output is correct
9 Correct 2 ms 1956 KB Output is correct
10 Correct 4 ms 1956 KB Output is correct
11 Correct 2 ms 1956 KB Output is correct
12 Correct 3 ms 1956 KB Output is correct
13 Correct 4 ms 1956 KB Output is correct
14 Correct 14 ms 1956 KB Output is correct
15 Correct 8 ms 1956 KB Output is correct
16 Correct 59 ms 1956 KB Output is correct
17 Correct 53 ms 1956 KB Output is correct
18 Correct 61 ms 1956 KB Output is correct
19 Correct 340 ms 2272 KB Output is correct
20 Correct 325 ms 2272 KB Output is correct