badFlamesへ @ 2022-07-08 20:29:20
这是
#include <bits/stdc++.h>
#define def register auto
#define LL long long
using namespace std;
const int N = 1e6 + 5;
inline LL read() {
LL x = 0, w = 0; char ch = getchar();
while(!isdigit(ch)) { w |= ch == 45; ch = getchar(); }
while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return w ? -x : x;
}
#define doge read()
int n, m;
LL sto_txn_orz;
int I_am_not_strong, I;
vector <int> Link[N], Lx[N];
int dfn[N], low[N], Ti;
int st[N], top, col[N], cnt, Lnode[N], Rnode[N], sz[N];
bool vis[N];
void tarjan(int u) {
dfn[u] = low[u] = ++Ti;
st[++top] = u; vis[u] = true;
for(auto v : Link[u]) {
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
cnt++; def v = 0;
do {
v = st[top--]; vis[v] = false;
col[v] = cnt;
sz[cnt]++;
} while(v != u);
}
}
LL f[N], ans;
int ind[N], outd[N];
LL bucket[N];
inline void sto(LL x) {
x = (x + sto_txn_orz) % sto_txn_orz;
}
set <int> vx[(int)2e5];
inline void Toposort() {
queue <int> Q;
for(def i = 1; i <= cnt; i++)
if(!ind[i]) {
Q.push(i);
sto(++bucket[sz[i]]);
}
while(!Q.empty()) {
def u = Q.front(); Q.pop();
f[u] += sz[u];
for(auto v : Lx[u]) {
f[v] = max(f[v], f[u]);
if(!outd[v]) {
sto(++bucket[f[v] + sz[v]]);
}
if(! --ind[v]) Q.push(v);
}
}
}
inline void Debug() {
printf("cnt = %d\n", cnt);
for(int i = 1; i <= n; i++) {
printf("col[%d] = %d\n", i, col[i]);
}
for(def i = 1; i <= cnt; i++) {
for(auto v : Lx[i]) {
printf("%d -> %d\n", i, v);
}
}
for(def i = 1; i <= 10; i++) {
printf("b[%d] = %d\n", i, bucket[i]);
}
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("Ans.txt", "w", stdout);
#endif
if(I_am_not_strong) {
while(true) I %= sto_txn_orz;
}
n = doge, m = doge, sto_txn_orz = doge;
for(def i = 1; i <= m; i++) {
def u = doge, v = doge;
Link[u].push_back(v);
Lnode[i] = u; Rnode[i] = v;
}
for(def i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
for(def i = 1; i <= m; i++) {
def x = col[Lnode[i]], y = col[Rnode[i]];
if(x != y) {
if(vx[x].find(y) != vx[x].end()) continue;
vx[x].insert(y);
Lx[x].push_back(y);
ind[y]++;
outd[x]++;
}
}
Toposort();
for(def i = 1; i <= cnt; i++) {
if(!outd[i]) ans = max(ans, f[i]);
}
//Debug();
cout << ans << endl << sto(bucket[ans]);
}
by Hoks @ 2023-02-04 19:19:33
@badFlamesへ 重边?