Cod sursa(job #1925705)

Utilizator enedumitruene dumitru enedumitru Data 13 martie 2017 16:36:13
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
ifstream f("trumplandia.in"); ofstream g("trumplandia.out");
int n,m,q;
struct art {int x,y,c,d,viz;} a[200010],sol[200010];
long long facut[200010];
int T[32][200010],Lev[200010];
int viz[200010],inv[200010],GR[200010];
vector <pair<int,int> > G[2*200010];
int grupa(int i)
{   if (GR[i] == i) return i;
    GR[i] = grupa(GR[i]);
    return GR[i];
}
void reuniune(int i,int j)
{   GR[grupa(i)]=grupa(j);}
int cmp(art h, art l)
{   if(h.c<l.c) return 1;
    return 0;
}
int lca(int x, int y)
{
    if(Lev[x] < Lev[y])
        swap(x, y);
    int log1, log2;
    for(log1 = 1; (1 << log1) < Lev[x]; ++log1);
    for(log2 = 1; (1 << log2) < Lev[y]; ++log2);
    for(int k = log1; k >= 0; --k)
        if(Lev[x] - (1 << k) >= Lev[y])
            x = T[k][x];
    if(x == y) return x;
    for(int k = log2; k >= 0; --k)
        if(T[k][x] && T[k][x] != T[k][y])
            x = T[k][x],
            y = T[k][y];
    return T[0][x];
}
void dfs(int nod, int lev)
{   Lev[nod]=lev; viz[nod]=1;
    vector <pair<int,int> > :: iterator it=G[nod].begin(),sf=G[nod].end();
    for(; it!=sf; it++)
        if(viz[(*it).x]==0) {T[0][(*it).x]=nod; dfs((*it).x, lev+1);}
}
int main()
{   f>>n>>m>>q;
    for(int i=1; i<=m; i++) {f>>a[i].x>>a[i].y>>a[i].c; a[i].d=i;}
    for(int i = 1;i <= n; ++i) GR[i]=i;
    sort(a+1,a+m+1,cmp);
    for(int i=1; i<=m; i++) inv[a[i].d]=i;
    long long ct=0,k=0;
    for(int i = 1;i <= m; ++i)
        if(grupa(a[i].x)!=grupa(a[i].y))
        {   ct=1LL*(ct+a[i].c);
            a[i].viz=1;
            sol[++k]=a[i];
            reuniune(a[i].x,a[i].y);
        }
    for(int i=1; i<=k; i++)
    {   G[sol[i].x].push_back(make_pair(sol[i].y,sol[i].c));
        G[sol[i].y].push_back(make_pair(sol[i].x,sol[i].c));
    }
    dfs(1,0);
    g<<ct<<'\n';
    for(k = 1; (1 << k) <= n; ++k)
        for(int i = 1; i <= n; ++i)
            T[k][i] = T[k-1][T[k-1][i]];
    for(int mc,i=1; i<=q; i++)
    {   f>>mc;
        int leg=inv[mc];
        if(a[leg].viz==1) g<<ct<<'\n';
        else
        {   if(facut[leg]!=0) g<<facut[leg]<<'\n';
            else
            {   int lc=lca(a[leg].x,a[leg].y);
                int cur=a[leg].x;
                int vmax=0;
                for(int k=0; (1<<k)<=n; ++k)
                    while(T[k][cur]!=0 and cur!=lc)
                    {   vector<pair<int,int> > :: iterator it=G[cur].begin(), sf=G[cur].end();
                        for(; it!=sf; it++)
                            if((*it).x==T[k][cur] and (*it).y>vmax) vmax=(*it).y;
                        cur=T[k][cur];
                    }
                cur=a[leg].y;
                for(int k=0; (1<<k)<=n; ++k)
                    while(T[k][cur]!=0 and cur!=lc)
                    {
                        vector<pair<int,int> > :: iterator it=G[cur].begin(), sf=G[cur].end();
                        for(; it!=sf; it++)
                            if((*it).x==T[k][cur] and (*it).y>vmax) vmax=(*it).y;
                        cur=T[k][cur];
                    }
                facut[leg]=1LL*(ct-vmax+a[leg].c);
                g<<facut[leg]<<'\n';
            }
        }
    }
    g.close(); return 0;
}