over 3 years ago

sigh数据真是坑爹

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#define l(x) (lct+x)

#define maxn 100001

#define maxm 1000001

#define maxq 200001

#define inf 1000000000

using namespace std;
int n,m,q,an=0,widen=0;
int query[maxq][3];
int next[maxm],p[maxn],u[maxm],v[maxm],w[maxm];
bool color[maxn];int ans[maxq],fa[maxn]={0};
struct node{int value,num;}a[maxm];
struct point
{
    point *fa,*son[2];
    int value,num,rev,zhi,xh;
    point(){value=zhi=-inf,num=xh=0,rev=0;}
    bool judge()
    {
        return this->fa->son[1]==this;
    }
    void pushup()
    {
        this->value=this->zhi;this->num=this->xh;
        if (this->value<max(this->son[0]->value,this->son[1]->value))
        {
            if ((this->son[0]->value)>(this->son[1]->value))
            {
                this->value=this->son[0]->value;
                this->num=this->son[0]->num;
            }
            else
            {
                this->value=this->son[1]->value;
                this->num=this->son[1]->num;
            }
        }
    }
    void pushdown()
    {
        if (rev)
        {
            swap(this->son[0],this->son[1]);
            rev=0;
            this->son[0]->rev^=1;this->son[1]->rev^=1;
        }
    }
    void setson(point *x,int r)
    {
        pushdown();
        this->son[r]=x;
        x->fa=this;
        pushup();
    }
    bool isroot();
}lct[maxn+maxm];
bool point::isroot()
{
    if (this->fa==lct) return true;
    return (this->fa->son[0]!=this&&this->fa->son[1]!=this);
}
inline void rot(point *now)
{
    point *p=now->fa;
    if (!now->fa->isroot()) now->fa->fa->pushdown();
    now->fa->pushdown();now->pushdown();
    int r=now->judge();
    p->setson(now->son[r^1],r);
    if (p->isroot()) 
    {
        now->fa=p->fa;
        now->setson(p,r^1);
    }
    else
    {
        point *grand=p->fa;int re=p->judge();
        now->setson(p,r^1);
        grand->setson(now,re);
    } 
}
inline void splay(point *now)
{
    if (now->isroot()) return;
    for (;!now->isroot();rot(now))
        if (now->fa->isroot());
        else if (now->judge()==now->fa->judge()) rot(now->fa);
            else rot(now);
}
  
inline point *access(point *now)
{
    point *y=lct;
    for (;now!=lct;y=now,now=now->fa)
    {
        splay(now);
        now->setson(y,1);
    }
    return y;
}
inline void changeroot(point *now)
{
    access(now)->rev^=1;
    splay(now);
}
inline void insert(point *x,point *y,point *z)
{
    changeroot(x);
    x->fa=z;
    changeroot(z);
    z->fa=y;
}
inline void delwide(point *x,point *y)
{
    changeroot(x);
    access(y);
    splay(x);
    x->son[1]=lct;
    y->fa=lct;
    x->pushup();
}
inline void del(point *x,point *y,point*z)
{
    delwide(x,z);
    delwide(z,y);
}
inline int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
inline void addedge(int x,int y,int z)
{
    widen++;next[widen]=p[x];p[x]=widen;
    v[widen]=y;w[widen]=z;u[widen]=x;
}
inline bool cmp(const node a,const node b)
{
    return a.value<b.value;
}
inline int find(int x)
{
    int y,now=x;
    for (;fa[now]!=now;)now=fa[now];
    for (;x!=fa[x];)
    {
        y=fa[x];
        fa[x]=now;
        x=y;
    }
    return now;
}
int main()
{
    int i,j,k,x,y,z,bj;
    memset(color,0,sizeof(color));
    n=readln();m=readln();q=readln();
    for (i=1;i<=n;i++) l(i)->fa=l(i)->son[0]=l(i)->son[1]=lct,l(i)->zhi=0,l(i)->xh=0;
    for (i=1;i<=m;i++)
    {
        x=readln();y=readln();z=readln();
        addedge(x,y,z);
        k=i+n;
        l(k)->fa=l(k)->son[0]=l(k)->son[1]=lct;
        l(k)->zhi=z,l(k)->xh=i;
    }
    for (i=1;i<=q;i++)
    {
        query[i][0]=readln();
        if (query[i][0]==2)
        {
            x=readln();y=readln();
            bj=0;
            for (k=p[x];k!=0;k=next[k])
                if (v[k]==y){
                    query[i][1]=k;
                    color[k]=1;
                    bj=1;break;
                    }
            if (bj==0)
                for (k=p[y];k!=0;k=next[k])
                if (v[k]==x)
                {
                    query[i][1]=k;
                    color[k]=1;break;
                }
        }
        else {query[i][1]=readln();query[i][2]=readln();}
    }
    for (k=1;k<=widen;k++)
    {
        if (color[k]==0)
        {
            a[++an].num=k;a[an].value=w[k];
        }
    }
    sort(a+1,a+an+1,cmp);
    for (i=1;i<=n;i++) fa[i]=i;
    for (i=1;i<=an;i++)
    {
        k=a[i].num;
        x=find(u[k]);y=find(v[k]);
        if (x!=y)
        { 
            insert(l(u[k]),l(v[k]),l(k+n));
            fa[x]=y;
        }
    }
    for (i=q;i>=1;i--)
    {
        if (query[i][0]==1)
        {
            changeroot(l(query[i][1]));
            ans[i]=access(l(query[i][2]))->value;
        }
        else
        {
            x=u[query[i][1]];
            y=v[query[i][1]];
            z=w[query[i][1]];
            changeroot(l(x));
            k=access(l(y))->num;
            if (w[k]>z)
            {
                del(l(u[k]),l(v[k]),l(k+n));
                insert(l(x),l(y),l(n+query[i][1]));
            }
        }
    }
    for (i=1;i<=q;i++)
    if (query[i][0]==1) printf("%d\n",ans[i]);
}
← 【poj1061】【数论】【扩展欧几里德+逆元】青蛙的约会 【bzoj1023】【仙人掌dp】cactus仙人掌图 →
 
comments powered by Disqus