Lvat_s Blog

sbLCT调了这么长时间……

Splay部分写错了

按照a从小到大排序，用LCT维护最小生成树

没了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=50005,INF=1000000000;

int n,m,ans=INF;

struct Node{
int v,id;
bool rev;
Node *ch[2],*fa,*mxe;
Node();
void Pushdown();
void Pushup();
}*tree[N<<2],*Null;

struct Ed{
int u,v,a,b;
friend bool operator<(const Ed &A,const Ed &B){return A.a<B.a||(A.a==B.a && A.b<B.b);}
}es[N<<1];

Node::Node(){fa=ch[0]=ch[1]=Null;mxe=this;v=-INF;rev=id=0;}

inline void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0],ch[1]);
    rev=0;
}
}

inline void Node::Pushup(){
mxe=this;
if(ch[0]->mxe->v>mxe->v)mxe=ch[0]->mxe;
if(ch[1]->mxe->v>mxe->v)mxe=ch[1]->mxe;
}

inline bool Notroot(Node *x){return x->fa->ch[0]==x || x->fa->ch[1]==x;}
inline void Prepare(Node *x){if(Notroot(x))Prepare(x->fa);x->Pushdown();}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
    if(!Notroot(y))Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
        else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
        else {Rotate(y,0);Rotate(x,0);}
    }
}
}

void Access(Node *x){for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}}
void Makeroot(Node *x){Access(x);Splay(x);x->rev^=1;}
void Link(Node *x,Node *y){Makeroot(x);x->fa=y;}
void Cut(Node *x,Node *y){Makeroot(x);Access(y);Splay(y);y->ch[0]=x->fa=Null;y->Pushup();}
Node *Find(Node *x){Access(x);Splay(x);while(x->ch[0]!=Null)x=x->ch[0];return x;}
Node *GetNull(){Node *p=new Node();p->ch[0]=p->ch[1]=p->fa=p->mxe=p;return p;}
Node *Query(Node *x,Node *y){Makeroot(x);Access(y);Splay(y);return y->mxe;}

int main(){
freopen("3.in","r",stdin);
freopen("3.out","w",stdout);
scanf("%d %d",&n,&m);
Null=GetNull();
for(int i=1;i<=m;i++)scanf("%d %d %d %d",&es[i].u,&es[i].v,&es[i].a,&es[i].b);
sort(es+1,es+m+1);
for(int i=1;i<=n;i++)tree[i]=new Node();
for(int i=1;i<=m;i++)tree[i+n]=new Node(),tree[i+n]->v=es[i].b,tree[i+n]->id=i;
for(int i=1;i<=m;i++){
    if(es[i].u==es[i].v)continue;
	if(Find(tree[es[i].u])==Find(tree[es[i].v])){
		Node *c=Query(tree[es[i].u],tree[es[i].v]);
		if(c->v>es[i].b){Cut(tree[es[c->id].u],c);Cut(tree[es[c->id].v],c);}
		else {if(Find(tree[1])==Find(tree[n]))ans=min(ans,es[i].a+Query(tree[1],tree[n])->v);continue;}
	}
    Link(tree[es[i].u],tree[i+n]);Link(tree[es[i].v],tree[i+n]);
    if(Find(tree[1])==Find(tree[n])){ans=min(ans,es[i].a+Query(tree[1],tree[n])->v);}
}
printf("%d\n",ans==INF?-1:ans);
return 0;
}