mcfx's blog

题解、Writeup、游记和碎碎念

BZOJ 4668: 冷战 LCT

1946 年 3 月 5 日，英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁幕演说”，正式拉开了冷战序幕。
美国和苏联同为世界上的“超级大国”，为了争夺世界霸权，两国及其盟国展开了数十年的斗争。在这段时期，虽然分歧和冲突严重，但双方都尽力避免世界范围的大规模战争（第三次世界大战）爆发，其对抗通常通过局部代理战争、科技和军备竞赛、太空竞争、外交竞争等“冷”方式进行，即“相互遏制，不动武力”，因此称之为“冷战”。
Reddington 是美国的海军上将。由于战争局势十分紧张，因此他需要时刻关注着苏联的各个活动，避免使自己的国家陷入困境。苏联在全球拥有 N 个军工厂，但由于规划不当，一开始这些军工厂之间是不存在铁路的，为了使武器制造更快，苏联决定修建若干条道路使得某些军工厂联通。
Reddington 得到了苏联的修建日程表，并且他需要时刻关注着某两个军工厂是否联通，以及最早在修建哪条道路时会联通。具体而言，现在总共有 M 个操作，操作分为两类：
• 0 u v，这次操作苏联会修建一条连接 u 号军工厂及 v 号军工厂的铁路，注意铁路都是双向的;
• 1 u v， Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第几条条铁路后会联通，假如到这次操作都没有联通，则输出 0;
作为美国最强科学家， Reddington 需要你帮忙设计一个程序，能满足他的要求。

Sample Output

0
3
5

Solution

直接用 LCT 维护动态最小生成树就行了，虽然很暴力，但能 AC。

Code

#include<bits/stdc++.h>

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
template<typename T> inline T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d)

const int N=1000001;

struct node
{
    node *c[2],*fa;
    int val,ma;
    bool rev;
    inline void rotate(bool f);
    inline void pushdown();
    inline void pushup();
}s[N],_null,*null=&_null;

inline void node::pushdown()
{
    if(fa->c[0]==this||fa->c[1]==this)
        fa->pushdown();
    if(rev)
    {
        rev=0;
        std::swap(c[0],c[1]);
        if(c[0]!=null)c[0]->rev=!c[0]->rev;
        if(c[1]!=null)c[1]->rev=!c[1]->rev;
    }
}

inline void node::rotate(bool f)
{
    fa->c[f]=c[!f];
    c[!f]=fa;
    fa=c[!f]->fa;
    if(c[!f]->fa->c[1]==c[!f])
        c[!f]->fa->c[1]=this;
    else if(c[!f]->fa->c[0]==c[!f])
        c[!f]->fa->c[0]=this;
    c[!f]->fa=this;
    c[!f]->c[f]->fa=c[!f];
    c[!f]->pushup();
}

inline void node::pushup()
{
    ma=val;
    if(c[0]!=null)repr(ma,c[0]->ma);
    if(c[1]!=null)repr(ma,c[1]->ma);
}

inline void init(node *x,int v)
{
    x->val=v,x->c[0]=null,x->c[1]=null,x->fa=null;
}

inline void splay(node *a)
{
    a->pushdown();
    while(a->fa->c[0]==a||a->fa->c[1]==a)
        a->rotate(a==a->fa->c[1]);
    a->pushup();
}

inline void access(node *a)
{
    node *x=null;
    while(a!=null)
    {
        splay(a);
        a->c[1]=x;
        a->pushup();
        x=a,a=a->fa;
    }
}

inline void movetoroot(node *x)
{
    access(x);
    splay(x);
    x->rev=!x->rev;
}

inline void link(node *x,node *y)
{
    movetoroot(x);
    x->fa=y;
}

inline void cut(node *x,node *y)
{
    movetoroot(x);
    access(y);
    splay(y);
    x->fa=null;
    y->c[0]=null;
    y->pushup();
}

inline void split(node *x,node *y)
{
    movetoroot(x),access(y),splay(y);
}

inline node* findroot(node *x)
{
    while(x->fa!=null)
        x=x->fa;
    return x;
}

int main()
{
    int n,m,lstans=0,opt,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        init(s+i,0);
    for(int i=1,ec=0;i<=m;i++)
    {
        scanf("%d%d%d",&opt,&x,&y);
        x^=lstans,y^=lstans;
        if(opt==0)
        {
            ec++;
            if(findroot(s+x)!=findroot(s+y))
            {
                init(s+n+ec,ec);
                link(s+x,s+n+ec);
                link(s+y,s+n+ec);
            }
        }
        else
        {
            split(s+x,s+y);
            if(findroot(s+x)==s+y)
                lstans=s[y].ma;
            else
                lstans=0;
            printf("%d\n",lstans);
        }
    }
}

日期： 2016-11-09
标签： BZOJ LCT
这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/72/ 查看。

mcfx's blog

BZOJ 4668: 冷战 LCT

Input

Output

Sample Input

Sample Output

Solution

Code