Cod sursa(job #2512536)

Utilizator altcontnoualt cont altcontnou Data 21 decembrie 2019 11:26:31
Problema Radiatie Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("radiatie.in");
ofstream g("radiatie.out");

int father[100005],depth[100005], n, m, a, b, tip, t, sa, sb;
struct d{
    int from, to, cost;
}muchii[400005];

int cost, nivel[100005];

vector<pair<int,int> >graph[100005];
pair<int,int>tata[100005];

class cmp{
public:
    bool operator()(d a, d b)
    {
        return a.cost<b.cost;
    }
};

int old_man(int ind)
{
    if (father[ind]==ind)
        return ind;
    return old_man(father[ind]);
}

void solve()
{
    int nod1, nod2, aux1, aux2;
    for (int i=1; i<=m; ++i)
    {
        nod1=muchii[i].from;
        nod2=muchii[i].to;
        aux1=old_man(nod1);
        aux2=old_man(nod2);
        if (aux1!=aux2)
        {
            if (depth[aux1]<depth[aux2])
                father[aux1]=aux2;
            else if (depth[aux2]<depth[aux1])
                father[aux2]=aux1;
            else
                father[aux1]=aux2,depth[aux2]++;
            cost+=muchii[i].cost;
            graph[nod1].push_back({nod2,muchii[i].cost});
            graph[nod2].push_back({nod1,muchii[i].cost});
        }
    }
}

void parcurgere(int ind)
{
    for (auto &v:graph[ind])
    {
        if (nivel[v.first]==0)
        {
            nivel[v.first]=nivel[ind]+1;
            tata[v.first]={ind,v.second};
            parcurgere(v.first);
        }
    }
}

void solvef()
{
    int cost_max=-1;
    for (int test=1; test<=t; ++test)
    {
        cost_max=-1;
        f >> a >> b;
        if (nivel[a]>nivel[b])
            swap(a,b);
        while(nivel[b]>nivel[a])
        {
            cost_max=max(cost_max,tata[b].second);
            b=tata[b].first;
        }
        while (a!=b)
        {
            cost_max=max(cost_max,tata[b].second);
            b=tata[b].first;
            cost_max=max(cost_max,tata[a].second);
            a=tata[a].first;
        }
        g << cost_max << '\n';
    }
}

int main()
{
    f >> n >> m >> t;
    for (int i=1; i<=n; ++i)
        father[i]=i, depth[i]=1;
    for (int i=1; i<=m; ++i)
        f >> muchii[i].from >> muchii[i].to >> muchii[i].cost;
    sort(muchii+1,muchii+m+1,cmp());
    solve();
    nivel[1]=1;
    parcurgere(1);
    solvef();
    return 0;
}