Cod sursă (job #817263)

#include <bits/stdc++.h>
using namespace std;
ifstream in("risipa.in");
ofstream out("risipa.out");
const int NMAX = (int)1e5 * 2;
long long N,M,start,A[NMAX],tm,component[NMAX],k,dp[NMAX],sum[NMAX];
vector<int>ad[NMAX],rad[NMAX],v,dag;
set<int>cad[NMAX];
bool b[NMAX];
void dfs(int node) {
	b[node] = true;
	for (int i : ad[node])
		if (!b[i])
			dfs(i);
	v.push_back(node);
	}

void dfs2(int node) {
	//cout << node << ' ';
	for (int i : rad[node])
		if (!component[i]) {
			component[i] = k;
			dfs2(i);
			}
	}

void dfs3(int node) {
	b[node] = true;
	for (auto i : cad[node])
		if (!b[i])
			dfs3(i);
	dag.push_back(node);
	}

void solve() {
	in >> N >> M >> start;
	for (int i = 1; i <= N;++i)
		in >> A[i];
	for (int i = 0; i < M;++i) {
		int u,v; in >> u >> v;
		ad[u].push_back(v);
		rad[v].push_back(u);
		}
	for (int i = 1; i <= N;++i)
		if (!b[i])
			dfs(i);
	reverse(v.begin(),v.end());
	for (int node : v)
		if (!component[node]) {
			component[node] = ++k;
			//cout << k << " -> ";
			dfs2(node);
			//cout << '\n';
			}
	for (int i = 1; i <= N;++i) {
		for (int j : ad[i]) 
			if (component[i] != component[j])
				cad[component[i]].insert(component[j]);
		sum[component[i]] += A[i];	
		b[i] = false;
		}
		
	dp[component[start]] = sum[component[start]];
	for (int i = 1; i <= k;++i)
		if (!b[i])
			dfs3(i);
	reverse(dag.begin(),dag.end());
	/*for (int i : dag) {
		cout << i << ' ' << sum[i] << '\n';
		for (int j : cad[i])
			cout << j << ' ';
		cout << '\n';
		}
	cout << '\n';*/
	for (int i : dag)
		if (dp[i])
			for (auto g : cad[i])
				dp[g] = max(dp[g],sum[g] + dp[i]);
	for (int i = 1; i <= N;++i)
		out << dp[component[i]] << '\n';
	}
// in nodul procesat curent in dfs2 nu mai intra nici un nod
main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
	}