Cod sursa(job #2656842)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 8 octombrie 2020 21:24:48
Problema Radiatie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.7 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("radiatie.in");
ofstream fout ("radiatie.out");

int tt[15001], rg[15001], lev[15001];
int ttt[14][15001], b[14][15001];
bool viz[15001];

struct latura
{
    int a, b, c;
}v[30001];

struct nod
{
    int info, cost;
    nod * urm;
}*vecin[30001];
nod * prim[30001];

int comparare(latura x, latura y)
{
    return x.c<y.c;
}
int find(int x)
{
    int r, y=x;
    while(tt[y]!=y)
    {
        y=tt[y];
    }
    r=y;
    //aplic compresia drumurilor
    while(tt[x]!=x)
    {
        y=tt[x];
        tt[x]=r;
        x=y;
    }
    return r;
}
void unite(int x, int y)
{
    if(rg[x]<rg[y])
    {
        tt[x]=y;
    }
    else
    {
        tt[y]=x;
    }
    if(rg[x]==rg[y])
    {
        rg[x]++;
    }
}
void DFS(int x, int lvl)
{
    viz[x]=1;
    lev[x]=lvl;
    nod * t=prim[x];
    while(t!=NULL)
    {
        if(!viz[t->info])
        {
            ttt[0][t->info]=x;
            b[0][t->info]=t->cost;
            DFS(t->info, lvl+1);
        }
        t=t->urm;
    }
}
int lca (int x, int y)
{
    int i, log1, log2, rez;
    if(lev[x]<lev[y])
    {
        swap(x, y);
    }
    //calculez log2 x si log2 y;
    for(log1=1; (1<<log1)<x; log1++);
    for(log2=1; (1<<log2)<y; log2++);
    //il aduc pe x la nivelul lui y;
    rez=0;
    for(i=log1; i>=0; i--)
    {
        if(lev[x]-(1<<i) >= lev[y])
        {
            rez=max(rez, b[i][x]);
            x=ttt[i][x];
        }
    }
    if(x==y) return rez;

    for(i=log2; i>=0; i--)
    {
        if(ttt[i][x] && ttt[i][x]!=ttt[i][y])
        {
            rez=max(rez, b[i][x]);
            x=ttt[i][x];

            rez=max(rez, b[i][y]);
            y=ttt[i][y];
        }
    }
    return max(b[0][y], max(rez, b[0][x]));
}

int main()
{
    int n, m, nrc, k, i, j, logn;
    fin>>n>>m>>nrc;

    for(i=1; i<=m; i++)
    {
        fin>>v[i].a>>v[i].b>>v[i].c;
    }

    sort(v+1, v+m+1, comparare);

    for(i=1; i<=n; i++)
    {
        tt[i]=i;
    }

    k=0;
    i=1;
    while(k<n-1)
    {
        int aux1=find(v[i].a);
        int aux2=find(v[i].b);
        if(aux1!=aux2)
        {
            k++;
            unite(aux1, aux2);

            //il adaug pe v[i].a la vecinii lui v[i].b si invers
            nod * aux = new nod;
            aux->info=v[i].a;
            aux->cost=v[i].c;
            aux->urm=NULL;

            if(prim[ v[i].b ]==NULL)
            {
                prim[ v[i].b ]=aux;
                vecin[ v[i].b ]=aux;
            }
            else
            {
                vecin[ v[i].b ]->urm=aux;
                vecin[ v[i].b ]=aux;
            }

            nod * aux2 = new nod;
            aux2->info=v[i].b;
            aux2->cost=v[i].c;
            aux2->urm=NULL;
            if(prim[ v[i].a ]==NULL)
            {
                prim[ v[i].a ]=aux2;
                vecin[ v[i].a ]=aux2;
            }
            else
            {
                vecin[ v[i].a ]->urm=aux2;
                vecin[ v[i].a ]=aux2;
            }

        }
        i++;
    }

    //il aleg arbitrar pe 1 ca radacina
    DFS(1, 0);

    /*for(i=1; i<=n; i++)
    {
        cout<<"lev["<<i<<"]= "<<lev[i]<<"\n";
    }
    cout<<"\n";*/

    for(logn=1; (1<<logn)<n; logn++);
    for(i=1; i<=logn; i++)
    {
        for(j=1; j<=n; j++)
        {
            ttt[i][j]=ttt[i-1][ ttt[i-1][j] ];
            b[i][j]=max(b[i-1][j], b[i-1][ ttt[i-1][j] ]);
        }
    }

    int x, y;
    for(i=1; i<=nrc; i++)
    {
        fin>>x>>y;
        fout<<lca(x, y)<<"\n";
    }
}