fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define show(x) cout << (#x) << " is " << (x) << endl
  5. #define ll long long
  6. #define len(s) (int)s.length()
  7. #define epb emplace_back
  8. #define fir first
  9. #define sed second
  10. #define sz(ds) (int)ds.size()
  11. #define all(arr) arr.begin(), arr.end()
  12.  
  13.  
  14. const int maxn = 1e6 + 5;
  15. int n, m, s, e;
  16. vector<int> adj[maxn], rv_adj[maxn];
  17. int pass[maxn];
  18. ll val[maxn];
  19.  
  20. vector<int> st;
  21.  
  22. vector<int> dag[maxn];
  23. vector< vector<int> > comps;
  24. int comp_of[maxn];
  25. ll sum_of[maxn];
  26. ll dp[maxn];
  27.  
  28. bool contain_e[maxn];
  29.  
  30. vector<int> ord;
  31.  
  32. void dfs_1(int u){
  33. 	pass[u] = true;
  34. 	for(auto v : adj[u]){
  35. 		if(!pass[v]) dfs_1(v);
  36. 	}
  37. 	ord.epb(u);
  38. }
  39.  
  40. void dfs_2(int u){
  41. 	pass[u] = true;
  42. 	st.epb(u);
  43. 	for(auto v : rv_adj[u]){
  44. 		if (!pass[v]) dfs_2(v);
  45. 	}
  46. }
  47.  
  48.  
  49. int main() {
  50. 	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  51. 	//
  52. 	cin >> n >> m >> s >> e;
  53. 	for (int i = 1 ; i <= n ; i++) cin >> val[i];
  54. 	for (int i = 0 ; i <  m ; i++) {
  55. 		int u, v;
  56. 		cin >> u >> v;
  57. 		adj[u].epb(v);
  58. 		rv_adj[v].epb(u);
  59. 	}
  60.  
  61.  
  62. 	for(int i = 1 ; i <= n ;i++){
  63. 		if(!pass[i])
  64. 			dfs_1(i);
  65. 	}
  66.  
  67. 	// dfs_1(s)
  68.  
  69. 	reverse(ord.begin(),ord.end());
  70.  
  71. 	fill(pass,pass+maxn,false);
  72.  
  73. 	for(auto i : ord){
  74. 		if(!pass[i]){
  75. 			dfs_2(i);
  76.  
  77. 			ll tmp = 0;
  78. 			ll nx_idx = sz(comps);
  79. 			for (auto v : st) {
  80. 				if (v == e) contain_e[nx_idx] = true;
  81. 				tmp += val[v];
  82. 				comp_of[v] = nx_idx;
  83. 			}
  84.  
  85. 			sum_of[nx_idx] = tmp;
  86.  
  87. 			comps.epb(st);
  88.  
  89. 			st.clear();
  90.  
  91. 		}
  92. 	}
  93.  
  94.  
  95. 	for (int i = 1 ; i <= n ; i++) {
  96. 		for (auto v : adj[i]) {
  97. 			int comp_i = comp_of[i];
  98. 			int comp_v = comp_of[v];
  99. 			if (comp_i != comp_v) {
  100. 				dag[comp_i].epb(comp_v);
  101. 			}
  102. 		}
  103. 	}
  104.  
  105. 	fill(pass,pass+maxn,false);
  106.  
  107. 	function<void(int,int)> dfs = [&](int u, int p){
  108.  
  109. 		pass[u] = true;
  110.  
  111. 		ll max_e = 0;
  112.  
  113. 		for(auto v : dag[u]){
  114. 			assert(v != p);
  115. 			if (!pass[v]){
  116. 				dfs(v,u);
  117. 			}
  118. 			if (contain_e[v]){
  119. 				max_e = max(max_e,dp[v]);
  120. 			}
  121. 		}
  122.  
  123. 		if(contain_e[u] || max_e > 0){
  124. 			dp[u] += (max_e + sum_of[u]);
  125. 			contain_e[u] = true;
  126. 		}
  127.  
  128.  
  129. 	};
  130.  
  131. 	dfs(comp_of[s], -1);
  132.  
  133. 	cout << dp[comp_of[s]];
  134.  
  135. }
Success #stdin #stdout 0.02s 81400KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6KwRpb
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!