Submission #2240135
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 GetMin()>>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(){
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();
if(e->GetRealMin()==1){
int a=e->v0(),b=e->v1();
int idx=e->GetIdx();
int x=c[idx],y=d[idx];
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 20:31:31+0900
Task
A - Cookie Exchanges
User
maroonrk
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
20117 Byte
Status
RE
Exec Time
102 ms
Memory
384 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 / 300
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, in2.txt, in3.txt, in4.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
RE
102 ms
256 KB
in10.txt
WA
1 ms
256 KB
in11.txt
RE
98 ms
256 KB
in2.txt
RE
97 ms
256 KB
in3.txt
RE
97 ms
256 KB
in4.txt
RE
97 ms
256 KB
in5.txt
RE
97 ms
256 KB
in6.txt
RE
98 ms
256 KB
in7.txt
RE
97 ms
256 KB
in8.txt
RE
98 ms
256 KB
in9.txt
RE
99 ms
256 KB
sample1.txt
RE
98 ms
256 KB
sample2.txt
RE
98 ms
256 KB
sample3.txt
RE
99 ms
384 KB