[Wc2006]水管局长&&[Wc2011] Xor

两道傻逼题无误……
所谓傻逼题,就是做了之后让你意识到你是傻逼的题
以上

挺好写的……一小时两题绝对够写了
水管局长bzoj上我tle了很久……
原因是太暴力……连做静态最小生成树都上lct……改成用Kruskal预处理后就a掉了……
用lct做和Kruskal做预处理最后都是O(mlgm),怎么想都是一样的嘛
而没有意识到自己太暴力之前……我一直在玩lct常数……

xor那题没什么好说的……都烂大街了
O(64m)的时间内弄出独立数就可以了
拓展一下就是……
http://poj.openjudge.cn/challenge4/D/
这题……

也是维护一下独立集合……专业术语叫啥来着……base?

tube.cpp
#include<cstdio>
#include<algorithm>
using namespace std;
#define M 1000005
#define N 500000
struct node{
    node*c[2],*p,*f,*opt;
    bool rev,isroot;int value;
    inline void flip(){swap(c[0],c[1]);rev^=1;}
    inline void push(){
        if(rev){
            if(c[0])c[0]->flip();
            if(c[1])c[1]->flip();
            rev=0;
        }
    }inline void maintain(){
        opt=this;
        if(c[0]&&c[0]->opt->value>opt->value)opt=c[0]->opt;
        if(c[1]&&c[1]->opt->value>opt->value)opt=c[1]->opt;
    }
}pool[N],*stp=pool,*R[N];
void rotate(node*o,int d){
    node*p=o->f,*q=p->f;
    p->c[d^1]=o->c[d];
    if(o->c[d])o->c[d]->f=p;
    o->c[d]=p;
    if(!q){
        p->isroot=0;o->p=p->p;p->p=NULL;o->isroot=1;
    }else{
        if(q->c[0]==p)q->c[0]=o;
        else q->c[1]=o;
    }o->f=q;p->f=o;
    p->maintain();
    o->maintain();
}void preview(node*o){
    if(!o)return;
    preview(o->f);
    o->push();
}void splay(node*x){
    for(preview(x);x->f;){
        if(x->f->f){
            node*y=x->f,*z=y->f;
            if(y==z->c[0]){
                if(x==y->c[0])rotate(y,1),rotate(x,1);
                else rotate(x,0),rotate(x,1);
            }else{
                if(x==y->c[1])rotate(y,0),rotate(x,0);
                else rotate(x,1),rotate(x,0);
            }
        }else{
            if(x->f->c[0]==x)rotate(x,1);
            else rotate(x,0);
        }
    }
}void cutRight(node*o,node*b){
    if(o->c[1])o->c[1]->isroot=1,o->c[1]->p=b,o->c[1]->f=NULL;
    o->c[1]=NULL;
}void linkRight(node*o,node*p){
    if(p)p->isroot=0,p->p=NULL,p->f=o;
    o->c[1]=p;
}void access(node*x){
    node*y=NULL;
    for(;x;x=x->p){
        splay(x);
        cutRight(x,x);
        linkRight(x,y);
        (y=x)->maintain();   
    }
}node*root(node*x){
    access(x);splay(x);
    node*y;
    for(;x;x=x->c[0])x->push(),y=x;
    return y;
}void makeroot(node*x){
    access(x);splay(x);
    x->flip();
}void link(node*x,node*y){
    makeroot(x);access(y);
    splay(y);x->p=y;   
}void cut(node*x,node*y){
    makeroot(x);
    access(y);
    cutRight(x,NULL);
    x->maintain();
}node* Query(node*u,node*v){
    makeroot(u);
    access(v);
    splay(u);
    return u->opt;
}bool used[M];
int n,m,q,top,ans[N],ufs[N],tmp[M];
int getfa(int u){
    return ufs[u]==u?u:(ufs[u]=getfa(ufs[u]));
}void Link(int u,int v,int w){
    node*x=R[u],*y=R[v],*z=Query(x,y);
    if(z->value>w){
        cut(z,y);cut(z,x);
        z->value=w;
        link(x,z);link(y,z);
    }
}struct edge{
    int u,v,w;bool used;
    bool operator <(const edge&rhs)const{
        return u<rhs.u||(u==rhs.u&&v<rhs.v);
    }
}E[M];bool cmp(const int&a,const int&b){
    return E[a].w<E[b].w;
}struct query{int typ,u,v;}Q[N];
int getint(){
    char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar());
    int tmp=0;
    for(;'0'<=ch&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';
    return tmp;
}int main(){
    n=getint();m=getint();q=getint();
    for(int i=1;i<=n;i++)R[i]=stp++,R[i]->opt=R[i],R[i]->isroot=1;
    for(int i=1;i<=m;i++)
    {
        E[i].u=getint();E[i].v=getint();E[i].w=getint();
        if(E[i].u>E[i].v)swap(E[i].u,E[i].v);
    }sort(E+1,E+1+m);
    for(int i=1;i<=q;i++){
        Q[i].typ=getint();Q[i].u=getint();Q[i].v=getint();
        if(Q[i].typ==2){
            if(Q[i].u>Q[i].v)swap(Q[i].u,Q[i].v);
            Q[i].u=lower_bound(E+1,E+1+m,(edge){Q[i].u,Q[i].v,0})-E;
            E[Q[i].u].used=1;
        }
    }for(int i=1;i<=n;i++)ufs[i]=i;
    for(int i=1;i<=m;i++)tmp[i]=i;
    sort(tmp+1,tmp+1+m,cmp);
    for(int i=1;i<=m;i++)
        if(!E[tmp[i]].used&&getfa(E[tmp[i]].u)!=getfa(E[tmp[i]].v))
        {
            node*z=stp++;z->value=E[tmp[i]].w;z->opt=z;
            link(R[E[tmp[i]].u],z);link(z,R[E[tmp[i]].v]);
            ufs[getfa(E[tmp[i]].v)]=getfa(E[tmp[i]].u);
        }
    for(int i=q;i>=1;i--){
        if(Q[i].typ==1)
            ans[++top]=Query(R[Q[i].u],R[Q[i].v])->value;
        else Link(E[Q[i].u].u,E[Q[i].u].v,E[Q[i].u].w);
    }for(int i=top;i;i--)
        printf("%d\n",ans[i]);
}

xor.cpp
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>
typedef long long LL;
using namespace std;
#define N 300000
queue<int>Q;
LL w,a[N],dis[N];
bool vis[N];
int n,m,cir;
vector<pair<int,LL> >G[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d%lld",&u,&v,&w);
        G[u].push_back(make_pair(v,w));
        G[v].push_back(make_pair(u,w));
    }for(Q.push(1),vis[1]=1;!Q.empty();Q.pop()){
        int u=Q.front();
        for(int i=0;i<G[u].size();i++)
            if(!vis[G[u][i].first]){
                vis[G[u][i].first]=1;
                dis[G[u][i].first]=dis[u]^G[u][i].second;
                Q.push(G[u][i].first);
            }else
                a[cir++]=dis[G[u][i].first]^dis[u]^G[u][i].second;
    }for(int i=62,rank=0;i>=0;i--){
        int pivot=rank;
        for(;pivot<cir;pivot++)
            if(a[pivot]>>i&1)
                break;
        if(pivot<cir){
            swap(a[rank],a[pivot]);
            for(int j=rank+1;j<cir;j++)
                if(a[j]>>i&1)
                    a[j]^=a[rank];
            rank++;
        }
    }LL ans=dis[n];
    for(int i=0;i<cir;i++)
        if((ans^a[i])>ans)
            ans^=a[i];
    cout<<ans<<endl;
}

Comments

comments powered by Disqus