蒟蒻求问

P2272 [ZJOI2007] 最大半连通子图

carp_oier @ 2023-09-21 20:27:18

我的代码老是这种数组大小导致这个要么T掉,要么WA。

请问一下下面这个代码正确的大小该是多少。

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define rl register ll
#define wl putchar('\n')
#define ws putchar(' ')

template <class T>

inline void r(T &res)
{
    char ch; bool f = 0;
    while((ch = getchar()) < '0' || ch > '9') f |= ch == '-';
    res = ch ^ 48;
    while((ch = getchar()) <= '9' && ch >= '0') res = (res << 1) + (res << 3) + (ch ^ 48);
    res = f ? ~res + 1 : res;
}

inline void ww(ll x)
{
    if(x < 0) putchar('-'), x = ~x + 1;
    if(x > 9) ww(x / 10);
    putchar(x % 10 ^ 48);
}

typedef long long LL;

const ll N = 2e6 + 10, M = 2e7 + 10;

ll n, m, mod;
ll h[N], hs[N], e[N], ne[N], tot;
ll dfn[N], timestamp, low[N];
ll stk[N], top;
bool in_stk[N];
ll id[N], scc_cnt, num[N];
ll f[N], g[N];

inline void add(ll a, ll b)
{
    ne[++tot] = h[a], h[a] = tot, e[tot] = b;
}

inline void addhs(ll a, ll b)
{
    ne[++tot] = hs[a], hs[a] = tot, e[tot] = b;
}

inline void tarjan(ll u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u, in_stk[u] = true;

    for(rl i=h[u]; i; i = ne[i])
    {
        ll v = e[i];
        if(!dfn[v]) 
            tarjan(v), low[u] = min(low[u], low[v]);
        else if(in_stk[v])
            low[u] = min(low[u], dfn[v]);
    }

    if(dfn[u] == low[u])
    {
        ++ scc_cnt;
        ll ele;
        do {
            ele = stk[top --], in_stk[ele] = false;
            id[ele] = scc_cnt;
            num[scc_cnt] ++;
        } while(u != ele);
    }
}

int main()
{
    r(n), r(m), r(mod);
    for(rl i=1; i <= m; ++ i)
    {
        ll a, b;
        r(a), r(b);
        add(a, b);
    }

    for(rl i=1; i <= n; ++ i)
        if(!dfn[i])
            tarjan(i);

    unordered_set<LL> S;        
    for(rl u=1; u <= n; ++ u)
        for(rl i=h[u]; i; i = ne[i])
        {
            ll v = e[i];
            ll a = id[u], b = id[v];
            LL hash = a * 1000000ll + b;
            if(a != b && !S.count(hash))
                addhs(a, b), S.insert(hash);
        }

    for(rl u=scc_cnt; u; -- u)
    {
        if(!f[u]) f[u] = num[u], g[u] = 1;
        for(rl i=hs[u]; i; i = ne[i])
        {
            ll v = e[i];
            if(f[v] < f[u] + num[v])
            {
                f[v] = f[u] + num[v];
                g[v] = g[u];
            } else if(f[v] == f[u] + num[v])   
                g[v] = (g[v] + g[u]) % mod;
        }
    }

    ll maxn = 0, sum = 0;

    for(rl i=1; i <= scc_cnt; ++ i)
        if(f[i] > maxn)
            maxn = f[i], sum = g[i];
        else if(f[i] == maxn) sum = (sum + g[i]) % mod;

    ww(maxn), wl, ww(sum), wl; 
    return 0;
}

by carp_oier @ 2023-09-21 20:28:11

@dayux 求助神犇


by carp_oier @ 2023-09-21 20:51:15

问题解决,此贴结


by carp_oier @ 2023-09-21 20:52:00

或许会让 dayux 白跑一趟


|