关于此题数组大小
查看原帖
关于此题数组大小
556955
123wbl楼主2024/10/1 11:35

我最开始用的清空原数组重建图,边数组开到6e6,其他是1e6,结果官方和民间数据最后四个点MLE和TLE,后面改了一下建图,用另一个数组存新图,点数组用5e5边用2e6炸了,后面一直提交,只改数组大小,提交记录改一次变一次,不是有点T了就是MLE或者WA,现在改到官方全过,民间最后四个点死活过不去,代码放下面,问一下各位大佬原因,也有可能是我的代码问题,有的话能不能帮忙指出一下,提交记录和源代码可以搜的到,我开了公开,最后一次的代码我放下面了

#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
struct node
{
    int to,next;
}e[6100101],e2[6100101];
int n,m,head[1000001],head2[1000001],tot=1,c[1000011],a[1000001];
int b[1000001],dcc[1000001],ans,dfn[1000001],low[1000001],id,siz[1000001];
ll f[1000001][2],mod=1e9+7,res;
inline void add(int u,int v)
{
    e[++tot].next=head[u];
    e[tot].to=v;
    head[u]=tot;
}
inline void add2(int u,int v)
{
	e2[++tot].next=head2[u];
	e2[tot].to=v;
	head2[u]=tot;
}
inline ll power(int x)
{
    ll base=2,res=1;
    while(x)
    {
        if(x&1) res=res*base%mod;
        base=base*base%mod;
        x>>=1;
    }
    return res;
}
inline void tarjan(int u,int in_edge)
{
    dfn[u]=low[u]=++id;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(!dfn[v])
        {
            tarjan(v,i);
            if(dfn[u]<low[v])
                b[i]=b[i^1]=1;
            low[u]=min(low[v],low[u]);
        }
        else
            if(i!=(in_edge^1))
                low[u]=min(dfn[v],low[u]);
    }
}
void dfs(int u)
{
    dcc[u]=ans;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(dcc[v]||b[i]) continue;
        dfs(v);
    }
}
void dfss(int u,int fa)
{
    siz[u]=c[u];
    for(int i=head2[u];i;i=e2[i].next)
    {
        int v=e2[i].to;
        if(v==fa) continue;
        dfss(v,u);
        siz[u]+=siz[v]+1;
    }
}
void dp(int u,int fa)
{
    for(int i=head2[u];i;i=e2[i].next)
    {
        int v=e2[i].to;
        if(v==fa) continue;
        dp(v,u);
        f[u][1]=(f[u][1]*(((f[v][0]<<1)+f[v][1])%mod)%mod+f[u][0]*f[v][1]%mod)%mod;
        f[u][0]=f[u][0]*((f[v][0]<<1)%mod)%mod;
    }
    if(u==1) res=(res+f[u][1])%mod;
    else res=(res+f[u][1]*power(siz[1]-siz[u]-1))%mod;
}
int main()
{
    std::cin.tie(0)->sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	int x,y;
        cin>>x>>y;
        if(x==y) continue;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i,0);
    for(int i=1;i<=n;i++)
        if(!dcc[i])
        {
            ++ans;
            dfs(i);
        }
    for(int i=1;i<=n;i++)
        a[dcc[i]]++;
    tot=1;
    for(int u=1;u<=n;u++)
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dcc[u]==dcc[v]) c[dcc[u]]++;
            else add2(dcc[u],dcc[v]);
        }
    for(int i=1;i<=ans;i++)
    {
        c[i]>>=1;
        f[i][0]=power(c[i]);
        f[i][1]=power(a[i]+c[i])-f[i][0];
    }
    dfss(1,0),dp(1,0);
    cout<<res;
}
2024/10/1 11:35
加载中...