求助简单并查集卡常

rt，最近在切水题，被水题切了

做法是先处理相等情况，然后不等情况与相等出现矛盾就无法满足，否则可以满足。

CPP

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000
int t,n;
map<int,int> to;
int p;
int fa[MAXN*2+10];
int x[MAXN+10],y[MAXN+10];
bool e[MAXN+10];
int f(int x){return fa[x]==x?x:f(fa[x]);}
signed main()
{
    //freopen("P1955_2.in","r",stdin);freopen("task.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    for(;t--;)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>x[i]>>y[i]>>e[i];
            to[x[i]]=to[y[i]]=0;
        }
        for(auto &i:to)i.second=++p;
        for(int i=1;i<=n;i++)x[i]=to[x[i]],y[i]=to[y[i]];
        for(int i=1;i<=p;i++)fa[i]=i;
        for(int i=1;i<=n;i++)if(e[i])fa[f(x[i])]=f(y[i]);
        bool flg=1;
        for(int i=1;i<=n;i++)
        {
            if(!e[i])
            {
                if(f(x[i])==f(y[i]))
                {
                    cout<<"NO\n";
                    flg=0;
                    break;
                }
            }
        }
        if(flg)cout<<"YES\n";
        p=0;
    }
}

RE了一个点，TLE两个点。清了to后变成了TLE三个点。

CPP

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200000
int t,n;
map<int,int> to;
int p;
int fa[MAXN*2+10];
int x[MAXN+10],y[MAXN+10];
bool e[MAXN+10];
int f(int x)
{
    for(;fa[x]!=x;x=fa[x]);
    return x;
}
signed main()
{
    //freopen("P1955_2.in","r",stdin);freopen("task.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    for(;t--;)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>x[i]>>y[i]>>e[i];
            to[x[i]]=to[y[i]]=0;
        }
        for(auto &i:to)i.second=++p;
        for(int i=1;i<=n;i++)x[i]=to[x[i]],y[i]=to[y[i]];
        for(int i=1;i<=p;i++)fa[i]=i;
        for(int i=1;i<=n;i++)if(e[i])fa[f(x[i])]=f(y[i]);
        bool flg=1;
        for(int i=1;i<=n;i++)
        {
            if(!e[i])
            {
                if(f(x[i])==f(y[i]))
                {
                    cout<<"NO\n";
                    flg=0;
                    break;
                }
            }
        }
        if(flg)cout<<"YES\n";
        to.clear();
        p=0;
    }
}

明明没开long long，并查集常数一般也跑不满吧。，放VS Code上用Code Runner运行一下点8跑了多次都是6.4s左右。

使用快读后运行大约在3.8s左右

CPP

#include<bits/stdc++.h>
using namespace std;
char buf[1<<17],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<16,stdin),p1==p2)?EOF:*p1++)
void qread(int &n)
{
    n=0;
    char c=0;
    bool f=0;
    for(;c<'0'||'9'<c;c=getchar())f=f|(c=='-');
    if(f)for(;'0'<=c&&c<='9';n=n*10+48-c,c=getchar());
    else for(;'0'<=c&&c<='9';n=n*10+c-48,c=getchar());
}
void qwrite(int n)
{
    char output[12]={};
    int top=0;
    if(n==0){putchar('0');return;}
    if(n<0){putchar('-');n=-n;}
    for(;n;output[40-(++top)]=n%10+48,n/=10);
    fwrite(output+40-top,1,top,stdout);
}
#define MAXN 100000
int t,n;
map<int,int> to;
int p;
int fa[MAXN*2+10];
int x[MAXN+10],y[MAXN+10];
int e[MAXN+10];
int f(int x)
{
    for(;fa[x]!=x;x=fa[x]);
    return x;
}
signed main()
{
    //freopen("P1955_8.in","r",stdin);freopen("task.out","w",stdout);
    //ios::sync_with_stdio(0);cin.tie(0);
    qread(t);
    for(;t--;)
    {
        qread(n);
        for(int i=1;i<=n;i++)
        {
            qread(x[i]),qread(y[i]),qread(e[i]);
            to[x[i]]=0;
            to[y[i]]=0;
        }
        for(auto &i:to)i.second=++p;
        for(int i=1;i<=n;i++)x[i]=to[x[i]],y[i]=to[y[i]];
        for(int i=1;i<=p;i++)fa[i]=i;
        for(int i=1;i<=n;i++)if(e[i])fa[f(x[i])]=f(y[i]);
        bool flg=1;
        for(int i=1;i<=n;i++)
        {
            if(!e[i])
            {
                if(f(x[i])==f(y[i]))
                {
                    printf("NO\n");
                    flg=0;
                    break;
                }
            }
        }
        if(flg)printf("YES\n");
        to.clear();
        p=0;
    }
}

有没有什么改动小的方法能卡过去，不太想改离散化，map常数比排序+lower_bound离散化常数大很多吗？

是不是我必须再加上启发式合并了、

求助简单并查集卡常

讨论操作

回复

相关推荐

求助简单并查集卡常