[HNOI2016]最小公倍数

C++14(g++5.4) 解法, 执行用时: 1364ms, 内存消耗: 5724K, 提交时间: 2019-10-29 22:09:34

// luogu-judger-enable-o2
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline void chkmax(int& x,int y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

struct Edge { int u,v,a,b; } e[N];
struct Query { int u,v,a,b,id; } q[N],o[N];
struct node { int u,v,a,b,sz; } sta[N];

inline int cmp1(Edge a,Edge b) { return a.a==b.a?a.b<b.b:a.a<b.a; }
inline int cmp2(Edge a,Edge b) { return a.b==b.b?a.a<b.a:a.b<b.b; }
inline int cmp3(Query a,Query b) { return a.b==b.b?a.a<b.a:a.b<b.b; }

int n,m,Q,top;
int ans[N];

struct UFS {
    int f[N],A[N],B[N],sz[N];
    inline void init(int n) {
        for (re int i=1;i<=n;++i) f[i]=i,A[i]=B[i]=-1,sz[i]=1;
    }
    inline int find(int x) { return x==f[x]?x:find(f[x]); }
    inline void merge(int x,int y,int a,int b) {
        x=find(x),y=find(y); if (sz[x]>sz[y]) swap(x,y);
        sta[++top]=(node){x,y,A[y],B[y],sz[y]};
        if (x!=y) f[x]=y,sz[y]+=sz[x],chkmax(A[y],A[x]),chkmax(B[y],B[x]);
        chkmax(A[y],a),chkmax(B[y],b);
    }
} S;

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) e[i]=(Edge){read(),read(),read(),read()};
    Q=read();
    for (re int i=1;i<=Q;++i) q[i]=(Query){read(),read(),read(),read(),i};
    sort(e+1,e+m+1,cmp1); sort(q+1,q+Q+1,cmp3);
    for (re int i=1,sz=sqrt(m);i<=m;i+=sz) {
        S.init(n); int sum=0;
        for (re int j=1;j<=Q;++j)
            if (e[i].a<=q[j].a&&(q[j].a<e[i+sz].a||i+sz>m))
                o[++sum]=q[j];
        if (!sum) continue;
        if (i!=1) sort(e+1,e+i,cmp2);
        for (re int j=1,k=1;j<=sum;++j) {
            //第一类
            while (k<i&&e[k].b<=o[j].b) {
                S.merge(e[k].u,e[k].v,e[k].a,e[k].b);
                ++k;
            }
            //第二类
            top=0;
            for (re int l=i;l<i+sz&&l<=m;++l)
                if (e[l].a<=o[j].a&&e[l].b<=o[j].b)
                    S.merge(e[l].u,e[l].v,e[l].a,e[l].b);
            int u=S.find(o[j].u),v=S.find(o[j].v);
            if (u==v&&S.A[u]==o[j].a&&S.B[u]==o[j].b) ans[o[j].id]=1;
            else ans[o[j].id]=0;
            //撤销
            while (top) {
                int u=sta[top].u,v=sta[top].v; S.f[u]=u;
                S.A[v]=sta[top].a,S.B[v]=sta[top].b,S.sz[v]=sta[top].sz;
                --top;
            }
        }
    }
    for (re int i=1;i<=Q;++i) puts(ans[i]?"Yes":"No");
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1405ms, 内存消耗: 5852K, 提交时间: 2023-03-31 20:07:48

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

const int N=100010;
struct node{
    int x,y,a,b,id;
    friend bool operator <(const node &a,const node &b){
        if(a.a==b.a) return a.b<b.b;
        return a.a<b.a;
    }
    void init(int k){
        id=k; scanf("%d%d%d%d",&x,&y,&a,&b);
    }
}e[N],q[N],tmp[N];
struct opt{
    int x,y,f,da,db,sz;
}op[N];
int ans[N],f[N],da[N],db[N],sz[N],Q,n,m,top,tot,x,y,S;

bool cmp(const node &a,const node &b){
    if(a.b==b.b) return a.a<b.a;
    return a.b<b.b;
}
int find(int x){
    return f[x]==x?x:find(f[x]);
}
void merge(int x,int y,int a,int b){
    x=find(x); y=find(y);
    if(sz[x]>sz[y]) swap(x,y);
    op[++tot].x=x; op[tot].da=da[y]; op[tot].db=db[y];
    op[tot].y=y; op[tot].f=f[x]; op[tot].sz=sz[y];
    if(x==y){
        da[x]=max(da[x],a); 
        db[x]=max(db[x],b); 
        return;
    }
    f[x]=y; sz[y]+=sz[x];
    da[y]=max(da[y],max(da[x],a));
    db[y]=max(db[y],max(db[x],b));
}
void Return(){
    for(;tot;tot--){
        f[op[tot].x]=op[tot].f;
        db[op[tot].y]=op[tot].db;
        da[op[tot].y]=op[tot].da;
        sz[op[tot].y]=op[tot].sz;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) e[i].init(i);
    sort(e+1,e+1+m);
    S=(int)sqrt(m);
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++) q[i].init(i);
    sort(q+1,q+1+Q,cmp);
    for(int i=1;i<=m;i+=S){
        top=0; 
        for(int j=1;j<=Q;j++)
        if(q[j].a>=e[i].a&&(i+S>m||q[j].a<e[i+S].a))
        tmp[++top]=q[j];
        sort(e+1,e+i,cmp);
        for(int j=1;j<=n;j++) f[j]=j,sz[j]=1,da[j]=db[j]=-1;
        for(int j=1,k=1;j<=top;j++){
            for(;k<i&&e[k].b<=tmp[j].b;k++)
            merge(e[k].x,e[k].y,e[k].a,e[k].b);
            tot=0;
            for(int l=i;l<i+S&&l<=m;l++)
            if(e[l].a<=tmp[j].a&&e[l].b<=tmp[j].b)
            merge(e[l].x,e[l].y,e[l].a,e[l].b);
            x=find(tmp[j].x); y=find(tmp[j].y);
            ans[tmp[j].id]=x==y&&da[x]==tmp[j].a&&db[x]==tmp[j].b;
            Return();
        }
    }
    for(int i=1;i<=Q;i++)
    if(ans[i]) puts("Yes");
    else puts("No");
    return 0;
}

详情