Cod sursa(job #3183289)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 11 decembrie 2023 14:02:30
Problema Radiatie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define sz 15000
using namespace std;
ifstream fin("radiatie.in");
ofstream fout("radiatie.out");

int n,m,k;

struct mch
{
    int x;
    int y;
    int c;
} mc[sz*2 + 5];

vector <int> v[sz + 5];

int t[sz + 5];
int c[sz + 5];
int lv[sz + 5];


int rad(int x)
{
    while(t[x] > 0)
        x=t[x];
    return x;
}


bool join(int x,int y,int cost)
{
    int rx = rad(x);
    int ry = rad(y);
    if(rx==ry)
        return false;
    if(-t[rx]<-t[ry])
    {
        swap(rx,ry);
    }
    c[ry] = cost;
    v[rx].push_back(ry);
    t[rx]+=t[ry];
    t[ry]=rx;
    return true;
}

void dfs(int nod,int l = 1)
{
    lv[nod]=l;
    for(auto& i : v[nod])
        dfs(i,l+1);
}


int main()
{
    fin>>n>>m>>k;
    for(int i=1; i<=n; i++)
        t[i]=-1;
    for(int i=1; i<=m; i++)
        fin>>mc[i].x>>mc[i].y>>mc[i].c;
    sort(mc+1,mc+m+1,[](mch a,mch b){return a.c<b.c;});

    for(int i=1; i<=m; i++)
        join(mc[i].x,mc[i].y,mc[i].c);
    int r = rad(mc[1].x);
    dfs(r);
    for(int i=1; i<=k; i++)
    {
        int x,y;
        fin>>x>>y;
        int s=-1;
        if(lv[x] > lv[y])
            swap(x,y);
        while(lv[y] != lv[x])
        {
            s=max(c[y],s);
            y=t[y];
        }
        if(y==x)
            fout<<s;
        else
        {
            s=max(s,c[y]);
            s=max(s,c[x]);
            fout<<s;
        }
        fout<<'\n';
    }
}