bzoj1093: [ZJOI2007]最大半连通子图

先缩点，重新建图，DP 就行了，类似于树形 DP，先求出从每个点出发，能走的最长链是多长，统计最长的那条就是最大半连通子图的点的数量

但是，超时，你妹，我也没办法

 

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
#include <stack>
#include <queue>
typedef long long LL;
typedef double DB;
typedef unsigned US;
typedef long double LDB;
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Ford(i, a, b) for(int i = (a); i >= (b); i--)
#define Rep(i, a) for(int i = (0); i < (a); i++)
#define Repn(i, a) for(int i = ((a) - 1); i >= 0; i--)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define repn(i, a, b) for(int i = ((a) - 1); i >= (b); i--)
#define FU(i, t) for(__typedef((t).begin()) i = (t).begin(); i != (t).end(); i++)
#define FD(i, t) for(__typedef((t).rbegin()) i = (t).rbegin(); i != (t).rend(); i++)
#define pi (3.141592653589793238)
#define MIT (2147483647)
#define INF (1000000000)
#define MLL (1000000000000000000LL)
#define ft first
#define sd second
#define mk make_pair
#define clr(a, x) (memset((a), (x), sizeof(a)))
#define sma_let(x) (((x) >= 'a') && ((x) <= 'z'))
#define big_let(x) (((x) >= 'A') && ((x) <= 'Z'))
#define let(x) ((sma_let(x)) || (big_let(x)))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define sqr(x) ((x) * (x))
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
inline void SETIO(string name) {
	string In = name + ".in", Out = name + ".out";
	freopen(In.c_str(), "r", stdin), freopen(Out.c_str(), "w", stdout);
}

const int N = 100010;
struct Edge {
	int v;
	Edge *Next;
	Edge() {}
	Edge(int _v, Edge *_Next) : v(_v), Next(_Next) {}
} *Fir[N], *First[N];
int n, m, Mod;
int Dfn[N], Low[N], Bel[N], Cnt, Tot, Vis[N], Val[N];
vector<int> Con[N];
stack<int> Stack;
int Count[N], Much[N], Dep[N], Ord[N];
queue<int> Q;

inline void Input() {
	scanf("%d%d%d", &n, &m, &Mod);
	int x, y;
	Rep(i, m) scanf("%d%d", &x, &y), Fir[x] = new Edge(y, Fir[x]);
}

inline void Tarjan(int u) {
	Dfn[u] = Low[u] = ++Cnt, Stack.push(u), Vis[u] = 1;
	for(Edge *Tab = Fir[u]; Tab != NULL; Tab = Tab->Next) {
		int v = Tab->v;
		if(!Dfn[v]) {
			Tarjan(v);
			Low[u] = min(Low[u], Low[v]);
		} else if(Vis[v]) Low[u] = min(Low[u], Dfn[v]);
	}
	
	if(Dfn[u] == Low[u]) {
		Val[++Tot] = 0;
		int x = -1;
		do {
			x = Stack.top();
			Val[Bel[x] = Tot]++, Con[Tot].pub(x);
			Vis[x] = 0, Stack.pop();
		} while(x != u);
	}
}

inline void Bfs(int S) {
	clr(Vis, 0);
	for(Q.push(S), Vis[S] = 1, Dep[S] = 1; sz(Q); ) {
		int u = Q.front(), v;
		Vis[u] = 0, Q.pop();
		for(Edge *Tab = First[u]; Tab != NULL; Tab = Tab->Next)
			if(Dep[v = Tab->v] < Dep[u] + 1) {
				Dep[v] = Dep[u] + 1;
				if(!Vis[v]) Vis[v] = 1, Q.push(v);
			}
	}
}

inline bool Cmp(int a, int b) { return Dep[a] > Dep[b]; }

inline void Solve() {
	For(i, 1, n)
		if(!Dfn[i]) Tarjan(i);
	
	// rebuild
	clr(Vis, 0), clr(Dfn, 0);
	For(i, 1, Tot)
		Rep(j, sz(Con[i])) {
			int u = Con[i][j], v;
			for(Edge *Tab = Fir[u]; Tab != NULL; Tab = Tab->Next)
				if(Vis[v = Bel[Tab->v]] != i && Bel[Tab->v] != i)
					First[i] = new Edge(v, First[i]), Vis[v] = i, Dfn[v]++;
		}
	
	// Work
	n = Tot + 1;
	For(i, 1, Tot)
		if(!Dfn[i]) First[n] = new Edge(i, First[n]);
	Bfs(n);
	For(i, 1, n) Ord[i] = i;
	sort(Ord + 1, Ord + 1 + n, Cmp);
	For(i, 1, n) {
		int u = Ord[i];
		Count[u] = 0, Much[u] = 0;
		for(Edge *Tab = First[u]; Tab != NULL; Tab = Tab->Next) {
			int v = Tab->v;
			if(Count[u] < Count[v]) Count[u] = Count[v], Much[u] = Much[v];
			else if(Count[u] == Count[v]) Much[u] = (Much[u] + Much[v]) % Mod;
		}
		Count[u] += Val[u], Much[u] = max(Much[u], 1);
	}
	
	// Get Ans
	printf("%d\n%d\n", Count[n], Much[n]);
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1093");
	#endif
	Input();
	Solve();
	return 0;
}