Cod sursă (job #816531)

#include "bits/stdc++.h"
#define int long long
const int mtestcase = 0;
#define debug(x) #x << " = " << x << '\n'
const int INF = (1 << 32);
const int SIZE = 1e5;
int comp[SIZE + 5], disc[SIZE + 5], low[SIZE + 5], cost[SIZE + 5], sum[SIZE + 5];
int timer, cnt, n, m, h;
std :: vector < int > dag[SIZE + 5];
std :: vector < int > adj[SIZE + 5];
std :: vector < int > dp, indeg, topo;
bool in_st[SIZE + 5], reach[SIZE + 5];
std :: stack < int > st;
int readInt() {
    int x;
    char ch;
    ch = fgetc(stdin);
    while (isspace(ch)) {
        ch = fgetc(stdin);
    }
    x = 0;
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = fgetc(stdin);
    }
    return x;
}
/// verificam nodurile accesibile
void Reach(int node){
  reach[node] = true;
  for(auto i : adj[node]){
    if(!reach[i]){
      Reach(i);
    }
  }
}
void Tarjan(int node){
  disc[node] = ++timer;
  low[node] = disc[node];
  st.push(node);
  in_st[node] = true;
  for(auto i : adj[node]){
    if(!reach[i]){
      continue;
    }
    if(!disc[i]){
      Tarjan(i);
      low[node] = std :: min(low[node], low[i]);
    }else if(in_st[i]){
      low[node] = std :: min(low[node], disc[i]);
    }
  }
  if(low[node] == disc[node]){
    cnt++;
    int topp = 0;
    while(true){
      topp = st.top();
      st.pop();
      in_st[topp] = false;
      comp[topp] = cnt;
      if(topp == node){
        break;
      }
    }
  }
}
void ReadInit(){
  //std :: cin >> n >> m >> h;
  n = readInt();
  m = readInt();
  h = readInt();
  for(int i = 1; i <= n; i++){
    //std :: cin >> cost[i];
    cost[i] = readInt();
  }
  for(int i = 1; i <= m; i++){
    int x, y;
    //std :: cin >> x >> y;
    x = readInt();
    y = readInt();
    adj[x].push_back(y);
    //adj[y].push_back(x);
  }
}
void Normalize(){
  for(int i = 1; i <= cnt; i++){
    std :: sort(dag[i].begin(), dag[i].end());
    dag[i].erase(std :: unique(dag[i].begin(), dag[i].end()), dag[i].end());
  }
}
void BuildDag(){
   Reach(h);
  for(int i = 1; i <= n; i++){
    if(reach[i] and disc[i] == 0){
      Tarjan(i);
    }
  }
  for(int i = 1; i <= n; i++){
    if(reach[i]){
      sum[comp[i]] += cost[i];
    }
  }
  for(int node = 1; node <= n; node++){
    if(!reach[node]){
      continue;
    }
    for(auto i : adj[node]){
      if(!reach[i]){
        continue;
      }
      if(comp[node] != comp[i]){
        dag[comp[node]].push_back(comp[i]);
      }
    }
  }

}
void testcase(){
  dp.resize(cnt + 1, -INF);
  indeg.resize(cnt + 1, 0);
  dp[comp[h]] = sum[comp[h]];
  for(int node = 1; node <= cnt; node++){
    for(auto i : dag[node]){
      indeg[i]++;
    }
  }
  // sortam topologic
  std :: queue < int > q;
  for(int i = 1; i <= cnt; i++){
    if(!indeg[i]){
      q.push(i);
    }
  }
  while(!q.empty()){
    int topp = q.front();
    q.pop();
    topo.push_back(topp);
    for(auto i : dag[topp]){
      indeg[i]--;
      if(!indeg[i]){
        q.push(i);
      }
    }
  }
  for(auto i : topo){
    if(dp[i] == -INF){
      continue;
    }
    for(auto j : dag[i]){
      dp[j] = std :: max(dp[j], dp[i] + sum[j]);
    }
  }
  for(int i = 1; i <= n; i++){
    if(!reach[i]){
      std :: cout << 0 << '\n';
    }else{
      std :: cout << dp[comp[i]] << '\n';
    }
  }
}
signed main(){
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  freopen("risipa.in", "r", stdin);
  freopen("risipa.out", "w", stdout);
  std :: ios_base :: sync_with_stdio(false);
  std :: cin.tie(0);
  if(mtestcase){
    int t;
    std :: cin >> t;
    while(t -- ){
      testcase();
    }
  }else{
    ReadInit();
    BuildDag();
    Normalize();
    testcase();
  }
  return 0;
}
/**
  exista muchie de la scc ul lui a si scc ul lui b daca exista muchie intre a si b
  dp[node] - suma maxima de cheltuieli pana in nodul node
*/