为什么全TLE

P2272 [ZJOI2007] 最大半连通子图

赵灵儿 @ 2018-04-03 19:45:45

#include <bits/stdc++.h>

using namespace std;

namespace program {
    typedef long long big;
    big next[1000005], to[1000005], head[1000005], Head[1000005], To[1000005], Next[1000005], Stack[100005], cnt, top, pre[100005], low[100005], query[100005], dp[100005];
    big tot1, tot2, now, cssno[100005], size[100005];
    big n, m, Mod, xx, yy, dis[100005], f[100005], MAXN, ans;

    template <class T>
    T read() {
        T s = 0;
        int ch;
        while (!isdigit(ch = getchar()));
        do
            s = s* 10 + ch - '0';
        while (isdigit(ch = getchar()));
        return s;
    }

    void add(big x, big y) {
        tot1 += 1;
        next[tot1] = head[x];
        to[tot1] = y;
        head[x] = tot1;                    
    }

    void Add(big x, big y) {
        tot2 += 1;
        Next[tot2] = Head[x];
        To[tot2] = y;
        Head[x] = tot2;
    }

    inline void dfs(big k) {
        cnt += 1;
        pre[k] = low[k] = cnt;
        top += 1;
        Stack[top] = k;
        for (big i = head[k]; i; i = next[i]) {
            big oo = to[i];
            if (!pre[oo]) {
                dfs(oo);
                low[k] = min(low[k], low[oo]);
            } else {
                if (!cssno[oo])
                    low[k] = min(low[k], low[oo]);
            }
        }
        if (low[k] == pre[k]) {
            now += 1;
            while (top) {
                big oo = Stack[top--];
                cssno[oo] = now;
                size[now] += 1;
                if (oo == k) 
                    break;
            }
        }
        return;
    }

    void work() {
        n = read<big>();
        m = read<big>();
        Mod = read<big>();
        for (big i = 1 ; i <= m; i++) {
            xx = read<big>();
            yy = read<big>();
            add(xx, yy);
        }
        for (big i = 1; i <= n; i++) {
            if (!pre[i])
                dfs(i);
        }
        for (big i = 1; i <= n; i++) {
            for (big j = head[i]; j; j = next[i]) {
                big oo = cssno[to[j]], ooo = cssno[i];
                if (oo != ooo) 
                    Add(ooo, oo), dis[oo] += 1;
            }
        }

        big vis[10005] = {0};
        big l = 1, r = 0;
        for (big i = 1; i <= now ; i++) {
            if (!dis[i])
                f[i] = size[i], dp[i] = 1, query[++r] = i;
        }

        while (l <= r) {
            big k = query[l], oo;
            for (big i = Head[k]; i ; i = Next[i]) {
                oo = To[i];
                dis[oo] -= 1;
                if (!dis[oo])
                    query[++r] = oo;
                if(vis[oo] == k)
                    continue;
                if (size[oo] + f[k] == f[oo])
                    dp[oo] = (dp[oo] + dp[k]) % Mod;
                if (size[oo] + f[k] > f[oo]) {
                    f[oo] =  f[k] + size[oo];
                    dp[oo] = dp[k] % Mod;
                }
                vis[oo] = k;
            }
            l += 1;
        }

        for (big i = 1; i <= now; i++) {
            if (f[i] == MAXN)
                ans = (ans + dp[i]) % Mod;
            if (f[i] > MAXN)
                MAXN = f[i], ans = dp[i] % Mod;
        }
        cout << MAXN << '\n' << ans << '\n';

        return;
    }
}

int main() {
    program::work();
    return 0;
}

|