Cod sursa(job #7319)

Utilizator wefgefAndrei Grigorean wefgef Data 21 ianuarie 2007 13:26:02
Problema Radiatie Scor 40
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasele 11-12 Marime 2.5 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define sch(a, b) a ^= b ^= a ^= b
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define pb push_back
#define sz size()

#define Nmax 15005
#define Mmax 30005

struct muc
{
	int a, b, c;
} M[Mmax];

int n, m, k;
int mult[Nmax], niv[Nmax];
char bun[Mmax], viz[Nmax];
vector<int> vec[Nmax], cost[Nmax];
int par[Nmax][16], pret[Nmax][16], level[Nmax];

void readdata()
{
	freopen("radiatie.in", "r", stdin);
	freopen("radiatie.out", "w", stdout);
	
	int i;
	scanf("%d %d %d", &n, &m, &k);
	for (i = 0; i < m; ++i)
		scanf("%d %d %d", &M[i].a, &M[i].b, &M[i].c);
}

int cmp(struct muc a, struct muc b)
{
	return a.c < b.c;
}

void uneste(int x, int y)
{
	if (niv[y] < niv[x]) mult[y] = x;
	else
	{
		if (niv[x] == niv[y]) ++niv[y];
		mult[x] = y;
	}
}

int find(int x)
{
	if (mult[x] != x) mult[x] = find(mult[x]);
	return mult[x];
}

void df(int k)
{
	int i, lim = vec[k].sz, nod, ind;
	
	nod = par[k][0];
	ind = 1;
	viz[k] = 1;
	while (nod)
	{
		if (par[nod][ind-1])
		{	
			par[k][ind] = par[nod][ind-1];
			pret[k][ind] = max(pret[k][ind-1], pret[nod][ind-1]);
		}
		nod = par[nod][ind-1];
		++ind;
	}
	for (i = 0; i < lim; ++i)
	{
		nod = vec[k][i];
		if (!viz[nod])
		{
			par[nod][0] = k;
			pret[nod][0] = cost[k][i];
			level[nod] = level[k]+1;
			df(nod);
		}
	}
}

void solve()
{
	int i, j, v1, v2, a, b, rez;
	int v[16];
	
	sort(M, M+m, cmp);
	for (i = 1; i <= n; ++i)
	{
		mult[i] = i;
		niv[i] = 1;
	}
	for (i = 0; i < m; ++i)
	{
		v1 = find(M[i].a);
		v2 = find(M[i].b);
		if (v1 != v2)
		{
			bun[i] = 1;
			uneste(v1, v2);
		}
	}
	for (i = 0; i < m; ++i)
	if (bun[i])
	{
		vec[M[i].a].pb(M[i].b);
		cost[M[i].a].pb(M[i].c);
		
		vec[M[i].b].pb(M[i].a);
		cost[M[i].b].pb(M[i].c);		
	}
	for (i = 1; i <= n; ++i)
	if (!viz[i]) df(i);

	for (j = 0; j < k; ++j)
	{
		scanf("%d %d", &a, &b);
		if (level[a] < level[b])
			sch(a, b);
		rez = 0;
		for (i = 15; i >= 0; --i)
			v[i] = ((level[a]-level[b]) >> i) & 1;
		for (i = 15; i >= 0; --i)
		if (v[i])
		{
			rez = max(rez, pret[a][i]);
			a = par[a][i];
		}
		for (i = 15; i >= 0; --i)
		if (par[a][i] != par[b][i])
		{
			rez = max(rez, pret[a][i]);
			rez = max(rez, pret[b][i]);
			a = par[a][i];
			b = par[b][i];
		}
		if (a != b)
			rez = max(rez, pret[a][0]);
		printf("%d\n", rez);
	}
}

int main()
{
	readdata();
	solve();
	return 0;
}