Submission #2239557
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
//#define int ll
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
//#undef MAROON_LOCAL
#ifdef MAROON_LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))
using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;
template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
os<<"("<<p.first<<","<<p.second<<")";
return os;
}
template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
os<<"[";
REP(i,(int)v.size()){
if(i)os<<",";
os<<v[i];
}
os<<"]";
return os;
}
ll read(){
ll i;
scanf("%" SCNd64,&i);
return i;
}
void printSpace(){
printf(" ");
}
void printEoln(){
printf("\n");
}
void print(ll x,int suc=1){
printf("%" PRId64,x);
if(suc==1)
printEoln();
if(suc==2)
printSpace();
}
string readString(){
static char buf[3341000];
scanf("%s",buf);
return string(buf);
}
char* readCharArray(){
static char buf[3341000];
static int bufUsed=0;
char* ret=buf+bufUsed;
scanf("%s",ret);
bufUsed+=strlen(ret)+1;
return ret;
}
template<class T,class U>
void chmax(T& a,U b){
if(a<b)
a=b;
}
template<class T,class U>
void chmin(T& a,U b){
if(b<a)
a=b;
}
template<class T>
T Sq(const T& t){
return t*t;
}
#define CAPITAL
void Yes(bool ex=true){
#ifdef CAPITAL
cout<<"YES"<<endl;
#else
cout<<"Yes"<<endl;
#endif
if(ex)exit(0);
}
void No(bool ex=true){
#ifdef CAPITAL
cout<<"NO"<<endl;
#else
cout<<"No"<<endl;
#endif
if(ex)exit(0);
}
const ll infLL=LLONG_MAX/3;
#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif
enum ClusterType{
NONE,
BASE,
RAKE,
COMPRESS,
HARDRAKE
};template<class ClusterInfoUtil>
struct TopTree{
using Info=typename ClusterInfoUtil::Info;
struct Cluster{
TopTree* belongingTree;
ClusterType type;
Cluster *l,*r,*m,*p;
Info info,tmpInfo;
int a,b;
Cluster(TopTree* tree):info(-1,-1),tmpInfo(-1,-1){
belongingTree=tree;
Clear();
}
void Clear(){
type=NONE;
l=nullptr;
r=nullptr;
m=nullptr;
p=nullptr;
info=Info(-1,-1);
tmpInfo=Info(-1,-1);
a=-1;
b=-1;
}
void UpdateHandles(){
if(type==BASE){
belongingTree->handles[a]=this;
belongingTree->handles[b]=this;
}else if(type==COMPRESS){
belongingTree->handles[l->a]=this;
belongingTree->handles[l->b]=this;
belongingTree->handles[r->a]=this;
belongingTree->handles[r->b]=this;
}
}
void Update(){
if(type==COMPRESS){
if(m){
tmpInfo=Info(l->a,l->b);
tmpInfo.Join(l->a,l->b,m->a,m->b,m->info,l->a,l->b,l->info,RAKE);
}
a=l->a;
b=r->b;
UpdateHandles();
info=Info(a,b);
info.Join(a,b,l->a,l->b,m?tmpInfo:l->info,r->a,r->b,r->info,COMPRESS);
}else if(type==RAKE){
a=r->a;
b=r->b;
info=Info(a,b);
info.Join(a,b,l->a,l->b,l->info,r->a,r->b,r->info,RAKE);
}else if(type==HARDRAKE){
int la=l->a,lb=l->b;
int ra=r->a,rb=r->b;
if(la==ra||la==rb)swap(la,lb);
if(lb==ra)swap(ra,rb);
a=ra;
b=rb;
info=Info(a,b);
info.Join(a,b,la,lb,l->info,ra,rb,r->info,RAKE);
}
}
void Reverse(){
swap(a,b);
}
void Normalize(){
if(type==BASE){
}else{
if(type==COMPRESS){
bool updMid=false;
if(r->a==a||r->b==a){
swap(l,r);
updMid=true;
}
if(l->a!=a)l->Reverse();
if(r->b!=b)r->Reverse();
if(m&&updMid){
tmpInfo=Info(l->a,l->b);
tmpInfo.Join(l->a,l->b,m->a,m->b,m->info,l->a,l->b,l->info,RAKE);
}
info.Split(a,b,l->a,l->b,m?tmpInfo:l->info,r->a,r->b,r->info,COMPRESS);
if(m)tmpInfo.Split(l->a,l->b,m->a,m->b,m->info,l->a,l->b,l->info,RAKE);
}else if(type==RAKE){
info.Split(a,b,l->a,l->b,l->info,r->a,r->b,r->info,RAKE);
}else if(type==HARDRAKE){
int la=l->a,lb=l->b;
int ra=r->a,rb=r->b;
if(la==ra||la==rb)swap(la,lb);
if(lb==ra)swap(ra,rb);
info.Split(a,b,la,lb,l->info,ra,rb,r->info,RAKE);
}
}
}
Cluster* Select(int&xa,int&xb,Info&x,int&ya,int&yb,Info&y){
Normalize();
if(type==BASE){
return this;
}else{
if(type==COMPRESS){
Info lTmp(l->b,l->a),rTmp(r->a,r->b);
if(xa==xb)lTmp=l->info;
else lTmp.Join(l->b,l->a,xa,xb,x,l->b,l->a,l->info,RAKE);
if(ya==yb)rTmp=r->info;
else rTmp.Join(r->a,r->b,yb,ya,y,r->a,r->b,r->info,RAKE);
if(m){
Info mTmp(l->a,l->b);
mTmp.Join(l->a,l->b,m->a,m->b,m->info,l->a,l->b,lTmp,RAKE);
bool s=Info::Select(l->a,l->b,mTmp,r->a,r->b,rTmp,COMPRESS);
if(s){
xa=l->a,xb=l->b,x=mTmp;
return r;
}else{
mTmp=Info(m->a,m->b);
mTmp.Join(m->a,m->b,r->b,r->a,rTmp,m->a,m->b,m->info,RAKE);
s=Info::Select(m->a,m->b,mTmp,l->a,l->b,lTmp,RAKE);
if(s){
ya=m->b,yb=m->a,y=mTmp;
return l;
}else{
Info lrTmp(r->b,r->a);
lrTmp.Join(r->b,r->a,l->a,l->b,lTmp,r->b,r->a,rTmp,RAKE);
xa=m->a,xb=m->a,x=Info(-1,-1),ya=r->a,yb=r->b,y=lrTmp;
return m;
}
}
}else{
bool s=Info::Select(l->a,l->b,lTmp,r->a,r->b,rTmp,COMPRESS);
if(s){
xa=l->a,xb=l->b,x=lTmp;
return r;
}
else{
ya=r->a,yb=r->b,y=rTmp;
return l;
}
}
}else if(type==RAKE){
Info w(l->a,l->b);
if(ya==yb)w=l->info;
else w.Join(l->a,l->b,yb,ya,y,l->a,l->b,l->info,RAKE);
bool s=Info::Select(l->a,l->b,w,r->a,r->b,r->info,RAKE);
if(s){
xa=r->a,xb=r->a,x=Info(-1,-1),ya=l->b,yb=l->a,y=w;
return r;
}else{
w=Info(r->a,r->b);
if(ya==yb)w=r->info;
else w.Join(r->a,r->b,yb,ya,y,r->a,r->b,r->info,RAKE);
xa=l->a,xb=l->a,x=Info(-1,-1),ya=r->b,yb=r->a,y=w;
return l;
}
}else if(type==HARDRAKE){
int la=l->a,lb=l->b;
int ra=r->a,rb=r->b;
if(la==ra||la==rb)swap(la,lb);
if(lb==ra)swap(ra,rb);
Info lTmp(la,lb),rTmp(ra,rb);
if(ya==yb)lTmp=l->info;
else lTmp.Join(la,lb,yb,ya,y,la,lb,l->info,RAKE);
if(xa==xb)rTmp=r->info;
else rTmp.Join(rb,ra,xa,xb,x,rb,ra,r->info,RAKE);
bool s=Info::Select(la,lb,lTmp,ra,rb,rTmp,RAKE);
if(s){
if(ra==r->a){
ya=lb,yb=la,y=lTmp;
return r;
}else{
ya=xb,yb=xa,y=x;
xa=la,xb=lb,x=lTmp;
return r;
}
}else{
lTmp=Info(ra,rb);
if(ya==yb)lTmp=rTmp;
else lTmp.Join(ra,rb,yb,ya,y,ra,rb,rTmp,RAKE);
if(la==l->a){
xa=la,xb=la,x=Info(-1,-1),ya=rb,yb=ra,y=lTmp;
return l;
}else{
xa=ra,xb=rb,x=lTmp,ya=la,yb=la,y=Info(-1,-1);
return l;
}
}
}
}
assert(false);
}
int Pos(){
Cluster *x=p;
if(!x)return 0;
else if(x->l==this)return -1;
else if(x->r==this)return 1;
else if(x->m==this)return -2;
assert(false);
}
bool LinkedToParent(){
return p&&(p->type!=type||p->m==this);
}
void Rotate(){
Cluster *q=p,*c;
if(Pos()==1){
c=l;
l=q;
q->r=c;
}else{
c=r;
r=q;
q->l=c;
}
if(c){
if(c->p)c->p=q;
}
int w=p->Pos();
p=p->p;
q->p=this;
Cluster *x=p;
if(x){
if(w==1)x->r=this;
else if(w==-1)x->l=this;
else if(w==-2)x->m=this;
}
q->Update();
}
void Splay(Cluster* guard){
while(p&&p!=guard&&!LinkedToParent()){
Cluster *q=p->p;
if(q&&q!=guard&&!p->LinkedToParent()){
if(Pos()==p->Pos()){
p->Rotate();
}else{
Rotate();
}
Rotate();
}else{
Rotate();
}
}
Update();
}
void Destroy(){
info.Destroy(a,b);
}
};
vector<Cluster*> handles;
vector<Cluster> clusterBuf;
vi ptrBuf;
vi deg;
vector<Cluster*> hardRakeClusters,needUpdateClusters;
Cluster* selectRoot;
TopTree(){}
TopTree(int n){
Init(n);
}
int vertNum,edgeNum;
void Init(int n){
int s=n*2+10;
clusterBuf=vector<Cluster>(s,Cluster(this));
REP(i,s)ptrBuf.PB(i);
deg=vi(n,0);
handles=vector<Cluster*>(n,nullptr);
vertNum=n;
edgeNum=0;
selectRoot=nullptr;
}
Cluster* GetNew(){
Cluster *res=clusterBuf.data()+ptrBuf.back();
ptrBuf.pop_back();
res->Clear();
return res;
}
void Recycle(Cluster* ptr){
ptrBuf.PB(ptr-clusterBuf.data());
}
void ClearHardRakeClusters(){
while(!hardRakeClusters.empty()){
Cluster* x=hardRakeClusters.back();
hardRakeClusters.pop_back();
x->Normalize();
Recycle(x);
}
while(!needUpdateClusters.empty()){
Cluster* x=needUpdateClusters.back();
needUpdateClusters.pop_back();
x->Update();
}
}
void Rectify(Cluster* x,Cluster* guard){
Cluster* p=x->p;
if(p!=nullptr){
Rectify(p,guard);
if(p==guard&&p->r==x){
p->Reverse();
p->Normalize();
}
}
x->Normalize();
}
Cluster* CreateCompressCluster(Cluster*l,Cluster*r,Cluster*m){
auto p=GetNew();
p->type=COMPRESS;
p->l=l;
l->p=p;
p->r=r;
r->p=p;
p->m=m;
if(m){
m->p=p;
}
p->Update();
return p;
}
Cluster* CreateRakeCluster(Cluster*l,Cluster*r){
if(!l)return r;
if(!r)return l;
auto p=GetNew();
p->type=RAKE;
p->l=l;
l->p=p;
p->r=r;
r->p=p;
p->Update();
return p;
}
Cluster* CreateHardRakeCluster(Cluster*l,Cluster*r){
if(!l)return r;
auto p=GetNew();
hardRakeClusters.PB(p);
p->type=HARDRAKE;
p->l=l;
p->r=r;
p->Update();
return p;
}
void SoftExpose(int v,Cluster* guard){
if(handles[v]==guard)return;
Rectify(handles[v],guard);
Cluster *x=handles[v],*tmp=x;
if(x->type==COMPRESS)x->Splay(guard);
while(x->LinkedToParent()){
Cluster* p=x->p;
if(p->type==RAKE){
p->Splay(nullptr);
if(x->p!=p)
x->p->Splay(p);
x=p;
}
x=x->p;
x->Splay(guard);
}
x=tmp;
while(x->LinkedToParent()){
Cluster* m=nullptr;
Cluster* y=x->p;
if(y->type==RAKE){
Cluster*p=x->p;
if(x->Pos()<0){
m=p->r;
}else{
m=p->l;
}
y=p->p;
if(y->type==RAKE){
Cluster*q=p->p;
if(p->Pos()<0){
m=CreateRakeCluster(m,q->r);
}else{
m=CreateRakeCluster(m,q->l);
}
y=q->p;
Recycle(q);
}
Recycle(p);
}
m=CreateRakeCluster(m,y->l);
y->l->UpdateHandles();
y->l=x;
x->p=y;
y->m=m;
m->p=y;
y->Update();
x=y;
}
if(tmp->type==BASE)tmp=tmp->p;
if(tmp){
tmp->Splay(guard);
}
if(guard)guard->Update();
}
bool SoftExpose(int a,int b){
if(deg[b]==0){
return false;
}else if(deg[a]==0){
SoftExpose(b,nullptr);
if(handles[b]->a==b){
handles[b]->Reverse();
handles[b]->Normalize();
}
return false;
}else if(deg[b]==1){
SoftExpose(b,nullptr);
if(handles[b]->a==b){
handles[b]->Reverse();
handles[b]->Normalize();
}
SoftExpose(a,nullptr);
if(handles[a]==handles[b]){
return true;
}else{
if(handles[a]->a==a){
handles[a]->Reverse();
handles[a]->Normalize();
}
return false;
}
}else{
SoftExpose(b,nullptr);
SoftExpose(a,handles[b]);
if(handles[a]==handles[b]){
if(handles[a]->b==a){
handles[a]->Reverse();
handles[a]->Normalize();
}
return true;
}else if(handles[a]==handles[b]->l){
return true;
}else{
if(handles[a]->a==a){
handles[a]->Reverse();
handles[a]->Normalize();
}
return false;
}
}
}
void SoftExpose(int v){
if(deg[v]==0){
//do nothing
}else{
SoftExpose(v,nullptr);
if(handles[v]->a==v){
handles[v]->Reverse();
handles[v]->Normalize();
}
}
}
Cluster* HardExpose(int a,int b){
if(deg[b]==1){
return handles[a];
}else if(deg[a]==1){
needUpdateClusters.PB(handles[b]);
auto x=handles[b]->l;
x=CreateHardRakeCluster(handles[b]->m,x);
x=CreateHardRakeCluster(handles[b]->r,x);
return x;
}else{
needUpdateClusters.PB(handles[b]);
needUpdateClusters.PB(handles[a]);
auto x=handles[a]->r;
x=CreateHardRakeCluster(handles[a]->l,x);
x=CreateHardRakeCluster(handles[a]->m,x);
x=CreateHardRakeCluster(handles[b]->m,x);
x=CreateHardRakeCluster(handles[b]->r,x);
return x;
}
}
Cluster* HardExpose(int v){
return HardExpose(handles[v]->a,v);
}
Cluster* ExposePath(int a,int b){
assert(!selectRoot);
ClearHardRakeClusters();
if(deg[a]>deg[b])swap(a,b);
bool connected=SoftExpose(a,b);
if(!connected)return nullptr;
return HardExpose(a,b);
}
Info* Expose(int a,int b){
//cerr<<"expose "<<a<<" "<<b<<endl;
if(a==b)return Expose(a);
Cluster*x=ExposePath(a,b);
if(x)return &(x->info);
else return nullptr;
}
Cluster* ExposeVertex(int v){
assert(!selectRoot);
ClearHardRakeClusters();
SoftExpose(v);
if(deg[v]==0)return nullptr;
return HardExpose(v);
}
Info* Expose(int v){
//cerr<<"expose "<<v<<endl;
Cluster*x=ExposeVertex(v);
if(x)return &(x->info);
else return nullptr;
}
bool Connected(int a,int b){
//cerr<<"connected "<<a<<" "<<b<<endl;
assert(!selectRoot);
ClearHardRakeClusters();
if(deg[a]>deg[b])swap(a,b);
return SoftExpose(a,b);
}
template <class... Args>
bool Link(int a,int b,Args... args){
assert(!selectRoot);
ClearHardRakeClusters();
if(deg[a]>deg[b])swap(a,b);
//cerr<<"link "<<a<<" "<<b<<endl;
bool connected=SoftExpose(a,b);
if(connected)return false;
Cluster* u=handles[a],*v=handles[b];
Cluster* x=GetNew();
x->type=BASE;
x->a=a;
x->b=b;
x->info=Info(a,b);
x->info.Create(a,b,args...);
x->UpdateHandles();
Cluster* y=nullptr;
if(deg[a]==0){
y=x;
}else if(deg[a]==1){
y=CreateCompressCluster(u,x,nullptr);
}else{
u->r->Reverse();
u->r->UpdateHandles();
y=CreateCompressCluster(u->l,x,CreateRakeCluster(u->r,u->m));
Recycle(u);
}
if(deg[b]==0){
}else if(deg[b]==1){
v->Reverse();
v->Normalize();
CreateCompressCluster(y,v,nullptr);
}else{
v->l->UpdateHandles();
CreateCompressCluster(y,v->r,CreateRakeCluster(v->m,v->l));
Recycle(v);
}
deg[a]++;
deg[b]++;
edgeNum++;
return true;
}
pair<Cluster*,Cluster*> SplitMiddleChild(Cluster*x){
if(x->type!=RAKE)return MP(x,nullptr);
while(x->type==RAKE)x=x->l;
x->p->Splay(nullptr);
Cluster* tmp=x->p;
pair<Cluster*,Cluster*> res=MP(tmp->l,tmp->r);
Recycle(tmp);
return res;
}
bool Cut(int a,int b){
assert(!selectRoot);
ClearHardRakeClusters();
if(deg[a]>deg[b])swap(a,b);
//cerr<<"cut "<<a<<" "<<b<<endl;
bool connected=SoftExpose(a,b);
if(!connected)return false;
Cluster *u=handles[a],*v=handles[b];
if(deg[b]==1){
if(u->type!=BASE)return false;
u->Destroy();
Recycle(u);
handles[a]=nullptr;
handles[b]=nullptr;
}else if(deg[a]==1){
if(v->l->type!=BASE)return false;
if(deg[b]==2){
v->r->p=nullptr;
v->r->UpdateHandles();
}else{
pair<Cluster*,Cluster*> z=SplitMiddleChild(v->m);
CreateCompressCluster(z.first,v->r,z.second);
}
v->l->Destroy();
Recycle(v->l);
Recycle(v);
handles[a]=nullptr;
}else{
if(u->r->type!=BASE)return false;
if(deg[a]==2){
u->l->p=nullptr;
u->l->UpdateHandles();
}else{
pair<Cluster*,Cluster*> z=SplitMiddleChild(u->m);
z.first->Reverse();
CreateCompressCluster(u->l,z.first,z.second);
}
if(deg[b]==2){
v->r->p=nullptr;
v->r->UpdateHandles();
}else{
pair<Cluster*,Cluster*> z=SplitMiddleChild(v->m);
CreateCompressCluster(z.first,v->r,z.second);
}
u->r->Destroy();
Recycle(u->r);
Recycle(u);
Recycle(v);
}
deg[a]--;
deg[b]--;
edgeNum--;
return true;
}
Info* PrepareForSelect(int a,int b){
//cerr<<"prepare "<<a<<" "<<b<<endl;
if(a==b)return PrepareForSelect(a);
selectRoot=ExposePath(a,b);
if(selectRoot==nullptr)return nullptr;
return &(selectRoot->info);
}
Info* PrepareForSelect(int v){
//cerr<<"prepare "<<v<<endl;
selectRoot=ExposeVertex(v);
if(selectRoot==nullptr)return nullptr;
return &(selectRoot->info);
}
Info* Select(){
assert(selectRoot);
assert(!selectRoot->p);
Cluster* cur=selectRoot;
int xa=cur->a,xb=xa,ya=cur->b,yb=ya;
Info x(-1,-1),y(-1,-1);
while(1){
Cluster*nx=cur->Select(xa,xb,x,ya,yb,y);
if(nx==cur)break;
cur=nx;
}
selectRoot=nullptr;
return Expose(cur->a,cur->b);
}
int NumofVertices(){
return vertNum;
}
int NumofEdges(){
return edgeNum;
}
};
struct InfoBase{
private:
int vert[2];
void SetVertex(int a,int b){
vert[0]=a;
vert[1]=b;
}
public:
InfoBase(int a,int b){
SetVertex(a,b);
}
inline int idx(int v){
if(vert[0]==v)return 0;
if(vert[1]==v)return 1;
assert(false);
}
inline int another(int v){
if(vert[0]==v)return vert[1];
if(vert[1]==v)return vert[0];
assert(false);
}
inline int v0(){
return vert[0];
}
inline int v1(){
return vert[1];
}
};
const int IndexBit=40;
struct Info:InfoBase{
ll m1,m2,lz;
Info(int a,int b):InfoBase(a,b){}
ll GetPathMin(){
return m1+lz;
}
ll GetNonPathMin(){
return m2;
}
ll GetMin(){
return min(GetPathMin(),GetNonPathMin());
}
ll GetRealMin(){
return GetPathMin()>>IndexBit;
}
ll GetIdx(){
return (m1+lz)&((1LL<<IndexBit)-1);
}
void Join(int a,int b,int la,int lb,Info&l,int ra,int rb,Info&r,ClusterType type){
//(another(a)==b);
//(another(b)==a);
if(type==RAKE){
//(a==ra);
//(b==rb);
//(lb==rb);
m1=r.GetPathMin();
m2=min(l.GetMin(),r.GetNonPathMin());
}else if(type==COMPRESS){
//(a==la);
//(lb==ra);
//(rb==b);
m1=min(l.GetPathMin(),r.GetPathMin());
m2=min(l.GetNonPathMin(),r.GetNonPathMin());
}
lz=0;
}
void Create(int a,int b,ll c){
//(another(a)==b);
//(another(b)==a);
m1=c;
m2=infLL;
lz=0;
}
void Split(int a,int b,int la,int lb,Info&l,int ra,int rb,Info&r,ClusterType type){
//(another(a)==b);
//(another(b)==a);
if(type==RAKE){
//(a==ra);
//(b==rb);
//(lb==rb);
r.lz+=lz;
}else if(type==COMPRESS){
//(a==la);
//(lb==ra);
//(rb==b);
l.lz+=lz;
r.lz+=lz;
}
m1+=lz;
lz=0;
}
void Destroy(int a,int b){
//(another(a)==b);
//(another(b)==a);
}
static bool Select(int la,int lb,Info l,int ra,int rb,Info r,ClusterType type){
if(type==RAKE){
//(lb==rb);
}else if(type==COMPRESS){
//(lb==ra);
}
return l.GetRealMin()>=r.GetRealMin();
assert(false);
}
};
signed main(){
cerr<<(1LL<<40)<<endl;
int n=read();
TopTree<Info> tree(n);
REP(i,n-1){
int a=read()-1,b=read()-1;
tree.Link(a,b,0);
}
vi c(n),d(n);
REP(i,n-1){
c[i]=read()-1,d[i]=read()-1;
tree.Expose(c[i],d[i])->lz+=(1LL<<IndexBit)+i;
}
REP(i,n-1){
tree.PrepareForSelect(0);
auto e=tree.Select();
int a=e->v0(),b=e->v1();
int idx=e->GetIdx(),x=c[idx],y=d[idx];
cerr<<e->m1+e->lz<<endl;
cerr<<e->GetMin()<<endl;
cerr<<a<<" "<<b<<" "<<x<<" "<<y<<" "<<e->GetRealMin()<<endl;
if(e->GetRealMin()==1){
tree.Cut(a,b);
tree.Link(a,b,infLL);
auto info=tree.Expose(x,y);
info->lz-=(1LL<<IndexBit)+idx;
}else{
No();
}
}
Yes();
}
Submission Info
Submission Time
2018-03-21 18:20:24+0900
Task
E - Blue and Red Tree
User
maroonrk
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
20255 Byte
Status
WA
Exec Time
397 ms
Memory
26484 KB
Compile Error
./Main.cpp: In function ‘ll read()’:
./Main.cpp:56:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%" SCNd64,&i);
^
./Main.cpp: In function ‘std::string readString()’:
./Main.cpp:78:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",buf);
^
./Main.cpp: In function ‘char* readCharArray()’:
./Main.cpp:86:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",ret);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 1400
Status
Set Name
Test Cases
Sample
sample1.txt, sample2.txt, sample3.txt
All
sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name
Status
Exec Time
Memory
in1.txt
AC
1 ms
256 KB
in10.txt
AC
382 ms
26484 KB
in11.txt
WA
290 ms
26484 KB
in12.txt
WA
292 ms
26484 KB
in13.txt
WA
295 ms
26484 KB
in14.txt
WA
293 ms
26484 KB
in15.txt
WA
295 ms
26484 KB
in16.txt
WA
293 ms
26484 KB
in17.txt
WA
292 ms
26484 KB
in18.txt
WA
300 ms
26484 KB
in19.txt
WA
290 ms
26484 KB
in2.txt
AC
1 ms
256 KB
in20.txt
WA
291 ms
26484 KB
in21.txt
AC
321 ms
26484 KB
in22.txt
AC
319 ms
26484 KB
in23.txt
AC
317 ms
26484 KB
in24.txt
AC
324 ms
26484 KB
in25.txt
AC
316 ms
26484 KB
in26.txt
AC
297 ms
26484 KB
in27.txt
WA
294 ms
26484 KB
in28.txt
WA
292 ms
26484 KB
in29.txt
WA
295 ms
26484 KB
in3.txt
AC
1 ms
256 KB
in30.txt
WA
298 ms
26484 KB
in31.txt
WA
267 ms
26484 KB
in32.txt
WA
264 ms
26484 KB
in33.txt
WA
266 ms
26484 KB
in34.txt
WA
260 ms
26484 KB
in35.txt
WA
261 ms
26484 KB
in36.txt
WA
262 ms
26484 KB
in37.txt
WA
269 ms
26484 KB
in38.txt
AC
360 ms
26484 KB
in39.txt
AC
335 ms
26484 KB
in4.txt
AC
385 ms
26484 KB
in40.txt
AC
332 ms
26484 KB
in41.txt
AC
262 ms
26484 KB
in42.txt
AC
262 ms
26484 KB
in43.txt
AC
261 ms
26484 KB
in44.txt
AC
260 ms
26484 KB
in45.txt
AC
261 ms
26484 KB
in46.txt
AC
220 ms
26484 KB
in47.txt
AC
207 ms
26484 KB
in5.txt
AC
397 ms
26484 KB
in6.txt
AC
216 ms
26484 KB
in7.txt
AC
381 ms
26484 KB
in8.txt
AC
384 ms
26484 KB
in9.txt
AC
382 ms
26484 KB
sample1.txt
AC
1 ms
256 KB
sample2.txt
AC
1 ms
256 KB
sample3.txt
AC
1 ms
256 KB