题目 P3387

#include<bits/stdc++.h>
#define int long long
#define PII pair< int, int >

using namespace std;

const int N = 1e5 + 5, mod = 998244353;
int n, m, a[N], h[N], e[N], ne[N], idx = 1, daan, in[N], h1[N], ans[N];
int dfn[N], low[N], clr, clrnum[N], cnt, flag[N];
bool vis[N], s[N];
PII edge[N];
stack< int > stk;

template< typename T >inline void read(T &x){bool f=1;x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x=(f?x:-x);return;}
template< typename T, typename ... L > void read(T &a , L && ... b) { read(a); read(b ...); }
int ksm(int a, int b, int p){int ans = 1;while(b){if(b & 1)ans =(ans*a)%p;b >>= 1;a = (a*a) % p;}return ans;}
void add(int h[], int u, int v){
	e[idx] = v;
	ne[idx] = h[u];
	h[u] = idx++;
}
void tarjan(int u){
	stk.push(u);
	vis[u] = s[u] = true;
	dfn[u] = low[u] = ++cnt;
	for (int i = h[u]; ~i; i = ne[i]){
		int v = e[i];
		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]){
		clr++;
		while (stk.top() != u){
			clrnum[clr]++;
			vis[stk.top()] = false;
			flag[stk.top()] = u;
			a[u] += a[stk.top()];
			stk.pop();
		}
		clrnum[clr]++;
		vis[stk.top()] = false;
		flag[stk.top()] = u;
		stk.pop();
	}
}
void topo(){
	queue< int > q;
	for (int i = 1; i <= n; i++){
		if (flag[i] == i && !in[i]){
			q.push(i);
			ans[i] = a[i];
		}
	}
	while (!q.empty()){
		int u = q.front();
		q.pop();
		for (int i = h1[u]; ~i; i = ne[i]){
			int v = e[i];
			ans[v] = max(ans[v], ans[u] + a[v]);
			if (!--in[v]) q.push(v);
		}
	}
} 
signed main(){
//	freopen("a.in", "r", stdin);
//	freopen("a.out","w",stdout);
	read(n, m);
	for (int i = 1; i <= n; i++) read(a[i]);
	memset(h, -1, sizeof h);
	memset(h1, -1, sizeof h1);
	for (int i = 1; i <= m; i++){
		int u, v;
		if (u == v) continue;
		read(u, v);
		edge[idx].first = u;
		edge[idx].second = v;
		add(h, u, v);
	}
	for (int i = 1; i <= n; i++){
		if (!s[i])
			tarjan(i);
	}
	for (int i = 1; i <= m; i++){
		int u = flag[edge[i].first], v = flag[edge[i].second];
		if (u == v) continue;
		add(h1, u, v);
		in[v]++;
	}
	topo(); 
	for (int i = 1; i <= n; i++) daan = max(daan, ans[i]);
	printf("%lld", daan);
	return 0;
}

我这段代码为什么开 O2 会 WA，但不开 O2 会 AC？