Pagini recente » Cod sursa (job #2830344) | Cod sursa (job #3128968) | Cod sursa (job #2227642) | Cod sursa (job #889196) | Cod sursa (job #3218940)
#include <iostream>
#include <fstream>
const int NMAX = 1e8;
int H[NMAX + 1];
int father(int nod)
{
return nod / 2;
}
int left_son(int nod)
{
return nod * 2;
}
int right_son(int nod)
{
return nod * 2 + 1;
}
void HeapUp(int K)
{
while (K > 1 && H[K] < H[father(K)])
{
std::swap(H[K], H[father(K)]);
K = father(K);
}
}
void HeapDown(int N, int K)
{
while (true)
{
int son = 0;
if (left_son(K) <= N)
{
son = left_son(K);
if (right_son(K) <= N && H[right_son(K)] < H[son])
{
son = right_son(K);
}
}
if (son && H[son] < H[K])
{
std::swap(H[son], H[K]);
K = son;
}
else
{
break;
}
}
}
void insert(int &N, int value)
{
H[++N] = value;
HeapUp(N);
}
int find_min()
{
return H[1];
}
void extract_min(int &N)
{
std::swap(H[1], H[N]);
N--;
HeapDown(N, 1);
}
void build(int N)
{
for (int i = N / 2; i >= 1; i--)
{
HeapDown(N, i);
}
}
void Delete(int &N, int K)
{
std::swap(H[K], H[N]);
N--;
if ((K > 1) && (H[K] < H[father(K)]))
{
HeapUp(K);
}
else
{
HeapDown(N, K);
}
}
void decrease_key(int K, int value)
{
H[K] -= value;
HeapUp(K);
}
void increase_key(int N, int K, int value)
{
H[K] += value;
HeapDown(N, K);
}
int main()
{
std::ifstream f("interclasari.in");
int nr_echipe;
f >> nr_echipe;
int heap_size = 0;
for (int i = 0, nr_poze, j, poza; i < nr_echipe; ++i)
{
f >> nr_poze;
for (j = 0; j < nr_poze; ++j)
{
f >> poza;
insert(heap_size, poza);
}
}
f.close();
std::ofstream g("interclasari.out");
g << heap_size << '\n';
while (heap_size > 0)
{
g << H[1] << ' ';
extract_min(heap_size);
}
g.close();
return 0;
}