Xopered @ 2021-09-06 20:49:06
record
我只输出了两行
#include<bits/stdc++.h>
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define ll long long
#define N 200005
#define M 1000005
using namespace std;
template<class T>void read(T&x) {
T f=1;x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=f;
}
template<class T>void write(T x) {
if(x<0)putchar('-'),x=-x;int s[20],top=0;
while(s[++top]=x%10,x/=10);
while(top)putchar(s[top--]+'0');putchar(' ');
}
template<class T,class...Ts>void write(T arg,Ts...args){write(arg);write(args...);}
template<class...Ts>void print(Ts...args){write(args...);putchar('\n');}
char _st;
int n,m,mod,cnt,h[N],dfn[N],low[N],step,SCC,bel[N],stk[N],top,ins[N],du[N],siz[N],dis[N],g[N];
struct Edge{int to,next;}e[M<<1];
void AddEdge(int x,int y){cnt++;e[cnt].to = y;e[cnt].next = h[x];h[x] = cnt;}
void dfs(int x) {
dfn[x] = low[x] = ++step;stk[++top] = x;ins[x] = 1;
for(int i=h[x]; i; i=e[i].next) {
int y = e[i].to;
if(!dfn[y])dfs(y),low[x] = min(low[x],low[y]);
else if(ins[y])low[x] = min(low[x],dfn[y]);
}
if(dfn[x] == low[x]) {
int t;SCC++;
do {
t = stk[top--];
ins[t] = 0;
bel[t] = SCC;
siz[SCC]++;
}while(t != x);
}
}
unordered_map<int,int>Mp[N];
vector<int>E[N];
char _ed;
int main() {
cerr << "Memory: " << abs((&_ed-&_st)>>20) << '\n';
read(n);read(m);read(mod);
for(int i=1,x,y; i<=m; ++i) {
read(x),read(y);
if(!Mp[x][y])AddEdge(x,y);
Mp[x][y] = 1;
}
for(int i=1; i<=n; ++i)if(!dfn[i])dfs(i);
for(int x=1; x<=n; ++x)
for(int i=h[x]; i; i=e[i].next) {
int y = e[i].to;
if(bel[x] != bel[y])E[bel[x]].push_back(bel[y]),du[bel[y]]++;
}
queue<int>q;
for(int i=1; i<=SCC; ++i)if(!du[i])q.push(i),dis[i] = siz[i],g[i] = 1;
while(!q.empty()) {
int x = q.front();q.pop();
for(int y:E[x]) {
if(dis[y] < dis[x]+siz[y])dis[y] = dis[x]+siz[y],g[y] = g[x];
else if(dis[y] == dis[x]+siz[y])g[y] = (g[y]+g[x])%mod;
if(!--du[y])q.push(y);
}
}
for(int i=1; i<=SCC; ++i) {
if(dis[0] < dis[i])dis[0] = dis[i],g[0] = g[i];
else if(dis[0] == dis[i])g[0] = (g[0]+g[i])%mod;
}
cout << dis[0] << '\n' << 114;
}
by Xopered @ 2021-09-06 20:52:37
怀疑luogu的judge出问题了
by rui_er @ 2021-09-06 20:56:47
把 cerr 删掉试试
by rui_er @ 2021-09-06 20:58:15
@Xopɐrɐd
by Xopered @ 2021-09-06 21:00:02
@rui_er 刚试了一发,不是cerr的问题
by GI录像机 @ 2022-04-22 10:16:13
@Xopɐrɐd 俺也一样