Cod sursa(job #1474635)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 22 august 2015 14:59:11
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include<bits/stdc++.h>
#define Lim 500000
#define Next (++pos==Lim)?(fin.read(Buffer,Lim),pos = 0):0
using namespace std;

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

const int NMAX=250005;
const int MMAX=500005;
const int LIMIT=1005;

int n,m,x,y,f[NMAX],comp[NMAX],rad[MMAX],sum[LIMIT];
int pos;
int a[MMAX],b[MMAX],c[MMAX];
char Buffer[Lim];

inline void Read(int &x)
{
    bool ok=0;
    while(Buffer[pos]<'0' || '9'<Buffer[pos])
        {
            if (Buffer[pos]=='-') ok=1;
            Next;
        }
    x = 0;
    while('0'<=Buffer[pos] && Buffer[pos]<='9')
    {
        x = x*10 +Buffer[pos]-'0';
        Next;
    }
    if (ok==1) x=-x;
}

inline void Union(int x,int y)
{
    if (comp[x]>comp[y])
        {
            f[y]=x;
            comp[x]+=comp[y];
        }
    else
        {
            f[x]=y;
            comp[y]+=comp[x];
        }
}

inline int Father(int x)
{
    int w,z;
    z=x;
    while (x!=f[x]) x=f[x];
    while (z!=f[z])
        {
            w=f[z];
            f[z]=x;
            z=w;
        }
    return x;
}

int main()
{
    int i,j,sol,ax,baux;
    Read(n);Read(m);Read(x);Read(y);
    for (i=1;i<=m;i++)
        {
            Read(a[i]);Read(b[i]);Read(c[i]);
            sum[c[i]]++;
        }
    for (i=1;i<LIMIT;i++) sum[i]+=sum[i-1];
    for (i=m;i>=1;i--)
        {
            rad[sum[c[i]]]=i;
            sum[c[i]]--;
        }
    for (i=1;i<=n;i++) {f[i]=i;comp[i]=1;}
    for (j=1;j<=m;j++)
        {
            i=rad[j];
            ax=Father(a[i]);baux=Father(b[i]);
            if (ax!=baux) Union(ax,baux);

            ax=Father(x);baux=Father(y);
            if (ax==baux) {sol=c[i];j=m+1;}
        }
    fout<<sol<<"\n";
    return 0;
}