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 白跑一趟