Cod sursa(job #461561)

Utilizator GotenAmza Catalin Goten Data 7 iunie 2010 15:27:45
Problema Radiatie Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include<fstream>
#include<vector>
#define max_n 15100
#define max_m 30100
using namespace std;
int a[max_m],b[max_m],c[max_m],h[max_m],gr[max_n],eu[2*max_n],niv[2*max_n],first[max_n],
	lg[max_n],rmq[16][max_n],res[16][max_n],padre[16][max_n];
int n,m,k,nr;
vector <pair <int, int> > v[max_n];
int cmp(int i, int j)
{
	return c[i]<c[j];
}
int group(int nod)
{
	if(gr[nod]==nod)
		return nod;
	else
	{
		int key=group(gr[nod]);
		gr[nod]=key;
		return key;
	}
}
void dfs(int nod, int pre, int nivel)
{
	eu[++eu[0]]=nod;
	padre[0][nod]=pre;
	niv[eu[0]]=nivel;
	if(!first[nod])
		first[nod]=eu[0];
	vector <pair <int, int> > :: iterator it;
	for(it=v[nod].begin();it!=v[nod].end();++it)
		if(!first[(*it).first])
		{
			res[0][(*it).first]=(*it).second;
			dfs((*it).first,nod,nivel+1);
		}
	if(pre)
	{
		eu[++eu[0]]=pre;
		niv[eu[0]]=nivel-1;
	}	
}
int main()
{
	int i,j,t,x,y,l,nod,r,xx,yy,ca,cb;
	ifstream read ("radiatie.in");
	ofstream write ("radiatie.out");
	read>>n>>m>>k;
	for(i=1;i<=m;++i)
	{
		read>>a[i]>>b[i]>>c[i];
		h[i]=i;
	}
	sort(h+1,h+m+1,cmp);
	for(i=1;i<=n;++i)
		gr[i]=i;
	for(i=1;i<=m&&nr<n-1;++i)
	{
		ca=cb=0;
		x=a[h[i]];
		y=b[h[i]];
		while(x!=gr[x])
		{
			x=gr[x];
			ca++;
		}
		while(y!=gr[y])
		{
			y=gr[y];
			cb++;
		}
		if(x!=y)
		{
			if(ca>cb)
				gr[y]=x;
			else
				gr[x]=y;
			nr++;
			v[a[h[i]]].push_back(make_pair(b[h[i]],c[h[i]]));
			v[b[h[i]]].push_back(make_pair(a[h[i]],c[h[i]]));
		}
	}
	dfs(1,0,0);
	lg[1]=0;
	for(i=2;i<=eu[0];i++)
		lg[i]=lg[i>>1]+1;
	for(i=1;i<=eu[0];i++)
		rmq[0][i]=i;
	for(j=1;j<=lg[eu[0]];j++)
		for(i=1;j<=lg[eu[0]+1-i];i++)
		{
			t=j-1;
			if(niv[rmq[t][i]]<niv[rmq[t][i+(1<<t)]])
				rmq[j][i]=rmq[t][i];
			else
				rmq[j][i]=rmq[t][i+(1<<t)];
		}
	for(j=1;j<=lg[n];++j)
		for(i=1;i<=n;++i)
		{
			t=j-1;
			if(res[t][i]<res[t][padre[t][i]])
				res[j][i]=res[t][padre[t][i]];
			else
				res[j][i]=res[t][i];
			padre[j][i]=padre[t][padre[t][i]];
		}
	while(k--)
	{
		r=0;
		read>>x>>y;
		xx=x;
		yy=y;
		x=first[x];
		y=first[y];
		if(x>y)
		{
			t=x;
			x=y;
			y=t;
			t=xx;
			xx=yy;
			yy=t;
		}
		l=lg[y-x+1];
		if(niv[rmq[l][x]]<niv[rmq[l][y+1-(1<<l)]])
			nod=rmq[l][x];
		else
			nod=rmq[l][y+1-(1<<l)];
		l=niv[x]-niv[nod];
		while(l)
		{
			r=max(r,res[lg[l]][xx]);
			xx=padre[lg[l]][xx];
			l-=(1<<lg[l]);
		}
		l=niv[y]-niv[nod];
		while(l)
		{
			r=max(r,res[lg[l]][yy]);
			yy=padre[lg[l]][yy];
			l-=(1<<lg[l]);
		}
		write<<r<<'\n';
	}
	return 0;
}