Cod sursa(job #2087076)

Utilizator GeanaVladGeana Vlad GeanaVlad Data 12 decembrie 2017 21:14:42
Problema Range minimum query Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.08 kb
#include <iostream>
#include<algorithm>
#include<fstream>
#include<vector>
using namespace std;
int n,m,i,q,gr[200010],M,ord,CT,sz_arb,vf[400010],nr_ord[400010],lev,lv[400010],vec,cst[400010],x,y,lca,tt[400010],x1,x2,j,p_a[400001];
int st[400010],sz,w[400001],d[400001][30],dp[400001][30],nr,lg2[400010];
bool viz[400010];
vector<int>v[400010];
ifstream f("trumplandia.in");
ofstream g("trumplandia.out");
struct muchie
{
    int x,y,c;
};
muchie c[200010],arb[200010],C[200010];
void buildRMQ()
{
    int i,j;
    for(i=1;i<=sz;i++)
        d[i][0]=i;
    for(j=0;(1<<j)<=sz;j++)
        for(i=1;i+(1<<j)<=sz+1;i++)
    {
        if(w[d[i][j]] < w[d[i+(1<<j)][j]])
            d[i][j+1] = d[i][j];
        else
            d[i][j+1]=d[i+(1<<j)][j];
    }
}
int querry(int i,int j)
{
    int k=log2(j-i+1);
    if(w[d[i][k]]<w[d[i-(1<<k)+1][k]])
        return d[i][k];
    else
        return d[i-(1<<k)+1][k];
}
int grupa(int i)
{
    if(gr[i]==i)
        return i;
    else
    {
        gr[i]=grupa(gr[i]);
        return gr[i];
    }
}
void reuniune(int i,int j)
{
    gr[grupa(i)]=grupa(j);
}
bool comp(muchie i,muchie j)
{
    return (i.c<=j.c);
}
bool cmp(int i,int j)
{
    return c[i].c<=c[j].c;
}
void dfs(int nod,int lev)
{
    viz[nod]=1;
    lv[nod]=lev;
    for(int k=0;k<v[nod].size();k++)
        if(!viz[v[nod][k]])
            dfs(v[nod][k],lev+1);
}
int varf(int nod)
{
    while(tt[nod])
        nod=tt[nod];
    return nod;
}
void parc_euler(int nod)
{
    st[++sz]=nod;
    if(p_a[nod]==0)
        p_a[nod]=sz;
    if(v[nod].size())
    {
        for(int k=0;k<v[nod].size();k++)
        parc_euler(v[nod][k]);
        st[++sz]=nod;
    }
}
int main()
{
    f>>n>>m>>q;
    for(i=1;i<=m;i++)
    {
        f>>c[i].x>>c[i].y>>c[i].c;
        C[i].x=c[i].x;
        C[i].y=c[i].y;
        C[i].c=c[i].c;
        nr_ord[i]=i;
    }
    sort(nr_ord+1,nr_ord+m+1,cmp);
    for(i=1;i<=2*n-1;i++)
        gr[i]=i;
    ord=n;
    M=m;
    sort(c+1,c+m+1,comp);
    for(i=1;i<=m;i++)
        if(grupa(c[i].x)!=grupa(c[i].y))
    {
        CT+=c[i].c;
        reuniune(c[i].x,c[i].y);
        arb[++sz_arb]=c[i];
        vf[i]=1;
    }
    g<<CT<<'\n';
    for(i=1;i<=2*n-1;i++)
        gr[i]=i;
    for(i=1;i<=sz_arb;i++)
    {
        //if(grupa(arb[i].x)!=grupa(arb[i].y))
        {
            ord++;
            x1=varf(c[i].x);
            x2=varf(c[i].y);
            v[ord].push_back(x1);
            v[ord].push_back(x2);
            tt[x1]=ord;
            tt[x2]=ord;
            cst[ord]=arb[i].c;
        }
    }
    parc_euler(ord);
    dfs(ord,1);
    for(i=1;i<=sz;i++)
    {
        int node=st[i];
        w[i]=lv[node];
    }
    lg2[1]=0;
    for(i=2;i<=sz;i++)
        lg2[i]=lg2[i/2]+1;
    buildRMQ();
    while(q--)
    {
        f>>nr;
        x=C[nr].x;
        y=C[nr].y;
        if(p_a[x]<p_a[y])
            lca=querry(p_a[x],p_a[y]);
        else
            lca=querry(p_a[y],p_a[x]);
        lca=st[lca];
        g<<CT - cst[lca] + C[nr].c<<'\n';
    }
}