bzoj1093:[ZJOI2007]最大半连通子图scc缩点+dag上dp

/**************************************************************Problem: 1093User: walfyLanguage: C&＃43;&＃43;Result: AcceptedTime:4788 msMemory:49420 kb
****************************************************************///#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune&＃61;native")
//#pragma GCC optimize("unroll-loops")
#include
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m&＃43;1,r,rt<<1|1
#define pil pair
#define pli pair
#define pii pair
#define cd complex
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g&＃61;10.0,eps&＃61;1e-11;
const int N&＃61;100000&＃43;10,maxn&＃61;1000000&＃43;10,inf&＃61;0x3f3f3f3f,INF&＃61;0x3f3f3f3f3f3f3f3f;int n,m,X;
stack<int>s;
vector<int>v[N],vv[N],ans[N];
int dfn[N],low[N];
int ins[N],inans[N];
int num,ind;
int a[maxn],b[maxn];
void tarjan(int u)
{ins[u]&＃61;2;low[u]&＃61;dfn[u]&＃61;&＃43;&＃43;ind;s.push(u);for(int i&＃61;0;i){int t&＃61;v[u][i];if(dfn[t]&＃61;&＃61;0){tarjan(t);low[u]&＃61;min(low[u],low[t]);}else if(ins[t]&＃61;&＃61;2)low[u]&＃61;min(low[u],dfn[t]);}if(low[u]&＃61;&＃61;dfn[u]){&＃43;&＃43;num;while(!s.empty()){int k&＃61;s.top();s.pop();ins[k]&＃61;1;ans[num].push_back(k);inans[k]&＃61;num;if(k&＃61;&＃61;u)break;}}
}
mapint>ma;
void scc()
{for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)if(!dfn[i])tarjan(i);for(int i&＃61;0;i){int x&＃61;inans[a[i]],y&＃61;inans[b[i]];if(x!&＃61;y&&!ma[mp(x,y)])vv[x].pb(y),ma[mp(x,y)]&＃61;1;}
}
pii dp[N];
pii DP(int u)
{if(dp[u].fi!&＃61;-1)return dp[u];dp[u].fi&＃61;ans[u].size(),dp[u].se&＃61;1;for(int i&＃61;0;i){int x&＃61;vv[u][i];pii te&＃61;DP(x);if(dp[u].fians[u].size()){dp[u]&＃61;te,dp[u].fi&＃61;te.fi&＃43;ans[u].size();
// printf("%d %d %d %d\n",u,x,dp[u].fi,dp[u].se);
}else if(dp[u].fi&＃61;&＃61;te.fi&＃43;ans[u].size()){dp[u].se&＃61;(dp[u].se&＃43;te.se)%X;
// printf("%d %d %d &＃43;&＃43;&＃43;%d\n",u,x,dp[u].se,te.se);
}}return dp[u];
}
int main()
{scanf("%d%d%d",&n,&m,&X);for(int i&＃61;0;i){scanf("%d%d",&a[i],&b[i]);v[a[i]].pb(b[i]);}scc();memset(dp,-1,sizeof dp);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)DP(i);int ma&＃61;0;for(int i&＃61;1;i<&＃61;num;i&＃43;&＃43;)ma&＃61;max(ma,dp[i].fi);//,printf("%d %d\n",dp[i].fi,dp[i].se);int ans&＃61;0;for(int i&＃61;1;i<&＃61;num;i&＃43;&＃43;)if(dp[i].fi&＃61;&＃61;ma)ans&＃61;(ans&＃43;dp[i].se)%X;printf("%d\n%d\n",ma,ans);return 0;
}
/**********************************************/