首页 > 代码库 > 2017.7.22 hnoi2016 最小公倍数
2017.7.22 hnoi2016 最小公倍数
#include<cmath> #include<cstdio> #include<iostream> #include<algorithm> #define N 50010 #define M 100010 #define RG register #define inf 0x3f3f3f3f using namespace std; bool ans[N]; struct stac{ int u,v,op; }sta[40000]; struct node{ int a,b,u,v,op; }one[M+N],two[M+N],edge[M+N]; int m,n,q,cnt,tim,tot,top1,top2,fa[N],siz[N],disa[N],disb[N],vala[N],valb[N]; inline int gi(){ RG int x=0;RG char c=getchar(); while(c<‘0‘||c>‘9‘) c=getchar(); while(c>=‘0‘&&c<=‘9‘) x=x*10+c-‘0‘,c=getchar(); return x; } inline bool cmp1(RG const node &a,RG const node &b){ if(a.a==b.a){ if(a.b==b.b) return a.op<b.op; return a.b<b.b; } return a.a<b.a; } inline bool cmp2(RG const node &a,RG const node &b){ if(a.b==b.b){ if(a.a==b.a) return a.op<b.op; return a.a<b.a; } return a.b<b.b; } inline int find(RG int x){ if(fa[x]==x) return x; return find(fa[x]); } inline int join(RG int u,RG int v,RG int a,RG int b,RG bool op){ RG int fau=find(u),fav=find(v); if(!op){ disa[fau]=max(a,disa[fau]); disb[fau]=max(b,disb[fau]); disa[fav]=max(a,disa[fav]); disb[fav]=max(b,disb[fav]); } else{ sta[++tim].u=fau; sta[tim].v=fav; sta[tim].op=0; vala[fau]=max(a,vala[fau]); valb[fau]=max(b,valb[fau]); vala[fav]=max(a,vala[fav]); valb[fav]=max(b,valb[fav]); } if(fau==fav) return tim; sta[tim].op=1; if(siz[fau]>siz[fav]){ fa[fav]=fau; siz[fau]+=siz[fav]; if(!op){ disa[fau]=max(disa[fau],disa[fav]); disb[fau]=max(disb[fau],disb[fav]); } else{ swap(sta[tim].u,sta[tim].v); vala[fau]=max(vala[fau],vala[fav]); valb[fau]=max(valb[fau],valb[fav]); } } else{ fa[fau]=fav; siz[fav]+=siz[fau]; if(!op){ disa[fav]=max(disa[fau],disa[fav]); disb[fav]=max(disb[fau],disb[fav]); } else{ vala[fav]=max(vala[fau],vala[fav]); valb[fav]=max(valb[fau],valb[fav]); } } return tim; } inline void del(RG int x){ if(sta[x].op){ siz[sta[x].v]-=siz[sta[x].u]; fa[sta[x].u]=sta[x].u; } vala[sta[x].u]=vala[sta[x].v]=valb[sta[x].u]=valb[sta[x].v]=-1; } int main(){ freopen("multiple.in","r",stdin); freopen("multiple.out","w",stdout); n=gi();m=gi(); for (RG int i=1;i<=m;++i){ edge[i].u=gi();edge[i].v=gi(); edge[i].a=gi();edge[i].b=gi(); } q=gi(); cnt=sqrt(m+q); tot=(m+q)/cnt+((m+q)%cnt>0); //printf("%d %d\n",cnt,tot); for (RG int i=1;i<=q;++i){ edge[i+m].op=i; edge[i+m].u=gi();edge[i+m].v=gi(); edge[i+m].a=gi();edge[i+m].b=gi(); } sort(edge+1,edge+m+q+1,cmp1); //for (RG int i=1;i<=m+q;++i) // printf("%d %d %d %d %d\n",edge[i].a,edge[i].b,edge[i].u,edge[i].v,edge[i].op); for (RG int i=1;i<=tot;++i){ top1=top2=0; for (RG int j=1;j<=n;++j){ fa[j]=j;siz[j]=1; disa[j]=disb[j]=-1; } for (RG int j=1;j<=min(i*cnt,m+q);++j) if(j<=(i-1)*cnt){ if(!edge[j].op) one[++top1]=edge[j]; } else if(edge[j].op) one[++top1]=edge[j]; else two[++top2]=edge[j]; sort(one+1,one+top1+1,cmp2); for (RG int j=1;j<=top1;++j){ if(!one[j].op) join(one[j].u,one[j].v,one[j].a,one[j].b,0); else{ tim=0; for (RG int k=1;k<=top2;++k) if(two[k].a<=one[j].a&&two[k].b<=one[j].b) two[k].op=join(two[k].u,two[k].v,two[k].a,two[k].b,1); RG int fau=find(one[j].u),fav=find(one[j].v); if(one[j].op==36){ printf("%d %d %d %d %d %d\n",fau,fav,one[j].a,max(disa[fau],vala[fau]),one[j].b,max(disb[fau],valb[fau])); // for (RG int i=1;i<=n;++i) printf("%d ",fa[i]); // cout<<endl; } if(fau==fav&&max(disa[fau],vala[fau])==one[j].a&&max(disb[fau],valb[fau])==one[j].b) ans[one[j].op]=1; for (RG int k=top2;k;--k) if(two[k].a<=one[j].a&&two[k].b<=one[j].b) del(two[k].op); } } } for (RG int i=1;i<=q;++i) if(ans[i]) printf("Yes\n"); else printf("No\n"); return 0; }
2017.7.22 hnoi2016 最小公倍数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。