Advertisement
Guest User

Untitled

a guest
Jan 15th, 2022
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.68 KB | None | 0 0
  1. // Snippets: https://github.com/prabhavdogra/CPSnippets;
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define int long long int
  5.  
  6. signed main() {
  7.     cin.tie(nullptr)->sync_with_stdio(false);
  8.     int n, m, s, e, u, v;
  9.     cin >> n >> m >> s >> e;
  10.     s--; e--;
  11.     vector<int> fun(n);
  12.     vector<vector<int>> adj(n);
  13.     for(auto &it: fun)
  14.         cin >> it;
  15.     for(int i = 0; i < m; i++) {
  16.         cin >> u >> v;
  17.         adj[u - 1].push_back(v - 1);
  18.     }
  19.     auto topo_dfs = [&] (vector<vector<int>> &adj_) -> vector<int> {
  20.         vector<int> vis(adj_.size());
  21.         vector<int> order_;
  22.         auto helper = [&] (const auto &self, int node) -> void {
  23.             vis[node] = 1;
  24.             for(auto &child: adj_[node])
  25.                 if(!vis[child])
  26.                     self(self, child);
  27.             order_.push_back(node);
  28.         };
  29.         for(int i = 0; i < n; i++)
  30.             if(!vis[i])
  31.                 helper(helper, i);
  32.         reverse(order_.begin(), order_.end());
  33.         return order_;
  34.     };
  35.     auto order = topo_dfs(adj);
  36.     auto scc = [&] (vector<vector<int>> adj_, vector<int> order_) -> vector<vector<int>> {
  37.         vector<vector<int>> radj_(adj_.size());
  38.         for(int i = 0; i < (int)adj_.size(); i++)
  39.             for(auto j: adj[i])
  40.                 radj_[j].push_back(i);
  41.         vector<vector<int>> components_;
  42.         auto vis = vector<int>(n, 0);
  43.         auto helper = [&] (const auto &self, int node) -> void {
  44.             vis[node] = 1;
  45.             components_.back().push_back(node);
  46.             for(auto child: radj_[node])
  47.                 if(!vis[child])
  48.                     self(self, child);
  49.         };
  50.         for(auto node: order) {
  51.             if(!vis[node]) {
  52.                 components_.push_back(vector<int>());
  53.                 helper(helper, node);
  54.             }
  55.         }
  56.         return components_;
  57.     };
  58.     auto components = scc(adj, order);
  59.     vector<int> num(n);
  60.     vector<int> color_(n);
  61.     auto condense = [&] (vector<vector<int>> adj_, vector<vector<int>> &components_) -> pair<vector<int>, vector<vector<int>>> {
  62.         vector<vector<int>> adj_scc_(adj_.size());
  63.         for(auto &component_: components_) {
  64.             int col_ = component_[0];
  65.             int res = 0;
  66.             for(auto it: component_) {
  67.                 color_[it] = col_;
  68.                 res += fun[it];
  69.             }
  70.             fun[col_] = res;
  71.         }
  72.         for(int i = 0; i < n; i++) {
  73.             for(auto j: adj_[i]) {
  74.                 if(color_[i] != color_[j])
  75.                     adj_scc_[color_[i]].push_back(color_[j]);
  76.             }
  77.         }
  78.         vector<int> order_scc_;
  79.         for(auto component_: components_)
  80.             order_scc_.push_back(component_[0]);
  81.         return {order_scc_, adj_scc_};
  82.     };
  83.     auto [order_scc, adj_scc] = condense(adj, components);
  84.     while(order_scc.size()) {
  85.         if(color_[e] != order_scc.back())
  86.             order_scc.pop_back();
  87.         else break;
  88.     }
  89.     vector<int> dp(n);
  90.     while(order_scc.size()) {
  91.         int x = order_scc.back();
  92.         order_scc.pop_back();
  93.         int val = 0;
  94.         for(auto neighour: adj_scc[x])
  95.             val = max(val, dp[neighour]);
  96.         dp[x] = val + fun[x];
  97.     }
  98.     cout << dp[color_[s]] << '\n';
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement