Cod sursa(job #1709973)

Utilizator TeamFIIBUAIC NoReturnValue TeamFIIB Data 28 mai 2016 14:39:07
Problema Revolta Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 3.18 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef struct celula{
   int nod;
	celula *next;
}*lista;

lista graf[100005],v;
int i,j,n,m,t;
int dmax1[100005], dmax2[100005], dim_max_sb1[100005], dim_max_sb2[100005], dmax_sus[100005], dim_max_sus[100005];
int sol;

void dfs1 (int nod, int t) {
	
	
	for (lista p = graf[nod]; p; p=p->next)
	 if (p->nod != t) dfs1(p->nod,nod);

	//
	int fmax1, dm1=0;
	
	for (lista p=graf[nod]; p; p=p->next)
	 if (p->nod!=t && dmax1[p->nod]+1>dm1) { dm1=dmax1[p->nod]+1; fmax1=p->nod; }
	 
	dmax1[nod]=dm1;
	
	int dm2=0, fmax2;
	
	for (lista p=graf[nod]; p; p=p->next)
	 if (p->nod!=t && p->nod!=fmax1 && dmax1[p->nod]+1>dm2) {
	    dm2=dmax1[p->nod]+1;
	    fmax2=p->nod;
	   }
	 
	dmax2[nod]=dm2;
	
	int diam_max_sb=dm1+dm2;
	int fmax=0;
	
	for (lista p=graf[nod]; p; p=p->next)
	 if (p->nod!=t && dim_max_sb1[p->nod]>diam_max_sb) { diam_max_sb=dim_max_sb1[p->nod]; fmax=p->nod; }
	 
	dim_max_sb1[nod]=diam_max_sb;
	 
	int diam_max_sb2=0;
	if (fmax==0) {
		
		for (lista p=graf[nod]; p; p=p->next)
	     if (p->nod!=t && p->nod!=fmax1 && p->nod!=fmax2 ) diam_max_sb2=max(diam_max_sb2,dim_max_sb1[p->nod]);
		
	}
	else {
		
		if (fmax!=fmax1 && fmax!=fmax2) {
	             diam_max_sb2=dm1+dm2;
        }
		
	   for (lista p=graf[nod]; p; p=p->next)
	     if (p->nod!=t && p->nod!=fmax) diam_max_sb2=max(diam_max_sb2,dim_max_sb1[p->nod]);

    }
	 
	dim_max_sb2[nod]=diam_max_sb2;
	 
}

void dfs2(int nod, int t) {
	
	//---
	
	dmax_sus[nod]=dmax_sus[t]+1;
	
	int aux=dmax1[t];
	if (aux==1+dmax1[nod]) aux=dmax2[t];
	
	dmax_sus[nod]=max(dmax_sus[nod],1+aux);
	
	//--
	
	dim_max_sus[nod]=dim_max_sus[t];
	
	if (aux!=0){
	dim_max_sus[nod]=max(dim_max_sus[nod],dmax_sus[t]+aux+1);
	
	if (dim_max_sb1[t]==dim_max_sb1[nod]) dim_max_sus[nod]=max(dim_max_sus[nod],dim_max_sb2[t]);
	else dim_max_sus[nod]=max(dim_max_sus[nod],dim_max_sb1[t]);
    }
    
    if (dim_max_sus[t]!=-1) {
    	
    	int mid1=(dim_max_sus[nod]+1)/2;
	    int mid2=(dim_max_sb1[nod]+1)/2;

        sol=min(sol,max(mid1+mid2+1,max(dim_max_sus[nod],dim_max_sb1[nod])));
    	
    }
    
    dim_max_sus[nod]=max(dim_max_sus[nod], max(dmax_sus[t],aux)+1 );
	
	//---
	for (lista p=graf[nod]; p; p=p->next)
	 if (p->nod!=t) dfs2(p->nod,nod);
	
}

int main(void) {

	ifstream cin("revolta.in");
	ofstream cout("revolta.out");
	
	cin>>t;
	
	for (; t; --t) {
		
		cin>>n;
		
		memset(graf,0,sizeof(graf));
		memset(dmax1,0,sizeof(dmax1));
		memset(dmax2,0,sizeof(dmax2));
		memset(dim_max_sb1,0,sizeof(dim_max_sb1));
		memset(dim_max_sb2,0,sizeof(dim_max_sb2));
		memset(dim_max_sus,0,sizeof(dim_max_sus));
		memset(dmax_sus,0,sizeof(dmax_sus));
		
		for (i=1; i<n; ++i) {
		 int x,y;
		 cin>>x>>y;
		 
		 ++x; ++y;
		 
		 v=new celula; v->nod=x; v->next=graf[y]; graf[y]=v;
		 v=new celula; v->nod=y; v->next=graf[x]; graf[x]=v;
			
		}
		
		dmax_sus[0]=-1;
		dim_max_sus[0]=-1;
		
		dmax1[0]=-1;
		dmax2[0]=-1;
		dim_max_sb1[0]=-1;
		dim_max_sb2[0]=-1;
		
		sol=1000000000;
		
		dfs1(1,0);
		dfs2(1,0);
		 
		cout<<sol<<"\n";
		
		
	}
	
	return 0;
}