Cod sursa(job #2504131)

Utilizator Cojocaru_Andrei_CristianCojocaru Andrei Cristian Cojocaru_Andrei_Cristian Data 4 decembrie 2019 15:25:19
Problema Radiatie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
#include <algorithm>
using namespace std;
struct boi
{
    int x,y,cost;
} v[400005];
int tata[200005],cnt[200005],cost[200005];
bool mycmp(boi a,boi b)
{
    return a.cost<b.cost;
}
bool verif(int nod1,int nod2)
{
    int cpn1=nod1,cpn2=nod2;
    while(nod1!=tata[nod1])
    {
        nod1=tata[nod1];
    }
    while(nod2!=tata[nod2])
    {
        nod2=tata[nod2];
    }
    if(nod1!=nod2)
    {
        if(cnt[nod1]==cnt[nod2])
        {
            cnt[nod1]++;
        }
        if(cnt[nod1]<cnt[nod2])
            {
                tata[nod1]=nod2;
                cost[nod1]=v[nod1].cost;
            }
        else
            {
            tata[nod2]=nod1;
            cost[nod2]=v[nod2].cost;
            }
        return 1;
    }
    else
    {
        return 0;
    }
}
int main()
{
    ifstream cin("radiatie.in");
    ofstream cout("radiatie.out");
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
       tata[i]=i;
    for(int i=1;i<=m;i++)
        cin>>v[i].x>>v[i].y>>v[i].cost;
    sort(v+1,v+m+1,mycmp);
    for(int i=1;i<=m;i++)
    {
        verif(v[i].x,v[i].y);
    }
    int t,u;
    for(int i=1;i<=q;i++)
    {
        cin>>t>>u;
        int ans=0;
        while(t!=u)
        {
            if(cnt[t]<cnt[u])
            {
                ans=max(ans,cost[t]);
                t=tata[t];
            }
            else
            {
                ans=max(ans,cost[u]);
                u=tata[u];
            }
        }
        cout<<ans;
    }
    return 0;
}