Cod sursă (job #816572)

// Author: Tanasescu Andrei-Rares
/*
     █████╗  ██████╗ ████████╗
    ██╔══██╗ ██╔══██╗╚══██╔══╝
    ███████║ ██████╔╝   ██║   
    ██╔══██║ ██╔══██╗   ██║   
    ██║  ██║ ██║  ██║   ██║   
    ╚═╝  ╚═╝ ╚═╝  ╚═╝   ╚═╝   
*/
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#include <cassert>

#pragma GCC optimize("O3")

#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;

ifstream fin ("risipa.in");
ofstream fout ("risipa.out");

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll Nmax=1e5+5, inf=1e9+5;

int n, m, h;
int v[Nmax];
ll sol[Nmax];
vector<int> ad[Nmax], adt[Nmax];
bool vis[Nmax];
int crt, cnt;
int ord[Nmax];
int clr[Nmax];

vector<vector<int>> ctc, adctc, adctct;
vector<int> gr, ts;
vector<ll> sumctc;

queue<int> q;
ll dp[Nmax];

void dfs1(int node){
    vis[node]=1;

    for (auto it:ad[node])
        if (!vis[it])
            dfs1(it);

    ord[crt++]=node;
}
void dfs2(int node){
    vis[node]=1;
    clr[node]=ctc.size()-1;
    ctc.back().pb(node);
    sumctc.back()+=v[node];

    for (auto it:adt[node])
        if (!vis[it])
            dfs2(it);
}
inline void Kosaraju(){
    for (int i=1; i<=n; i++)
        if (!vis[i])
            dfs1(i);
    
    for (int i=1; i<=n; i++)
        vis[i]=0;
    
    for (int i=n-1; i>=0; i--){
        int node=ord[i];
        if (!vis[node]){
            ctc.emplace_back();
            adctc.emplace_back();
            adctct.emplace_back();

            sumctc.pb(0);
            gr.pb(0);

            dfs2(node);
        }
    }
    cnt=ctc.size();
}

inline void Build_SCC_Graph(){
    for (int i=1; i<=n; i++){
        int a=clr[i];
        for (auto it:ad[i]){
            int b=clr[it];

            if (a!=b){
                adctc[a].pb(b);
                adctct[b].pb(a);
                gr[b]++;
            }
        }
    }
}

inline void Topological_Sort_SCC(){
    for (int i=0; i<cnt; i++)
        if (gr[i]==0)
            q.push(i);
    
    while (!q.empty()){
        int crt=q.front();
        q.pop();

        ts.pb(crt);
        for (auto it:adctc[crt]){
            gr[it]--;
            if (gr[it]==0)
                q.push(it);
        }
    }
}

inline bool has_h(int crt){
    bool ok=0;
    for (auto it:ctc[crt])
        if (it==h)
            ok=1;
    
    return ok;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    fin>>n>>m>>h;
    for (int i=1; i<=n; i++)
        fin>>v[i];
    
    for (int i=0; i<m; i++){
        int a, b;
        fin>>a>>b;
        ad[a].pb(b);
        adt[b].pb(a);
    }

    Kosaraju();
    Build_SCC_Graph();
    Topological_Sort_SCC();

    for (int i=0; i<cnt; i++){
        int crt=ts[i];

        ll mx=0;
        for (auto it:adctct[crt]){
            mx=max(mx, dp[it]);
        }
        
        if (mx==0){
            if (has_h(crt))
                mx=sumctc[crt];
        }
        else mx+=sumctc[crt];
        
        dp[crt]=mx;
        for (auto it:ctc[crt])
            sol[it]=mx;
    }

    for (int i=1; i<=n; i++)
        fout<<sol[i]<<'\n';

    return 0;
}