fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define all(x) (x).begin(),(x).end()
  4. using namespace std;
  5. const int N = 1e6 + 10;
  6. vector<int> g[N];
  7. vector<int> gr[N];
  8. vector<int> color(N);
  9. vector<int> dp(N);
  10. vector<int> comp_id(N);
  11. vector<int> fun(N);
  12. vector<int> fun_sum(N); // gives funsum of comp_id = i
  13. vector<int> order;
  14. int comp_number,st,en,a,b,n,m;
  15. void dfs1(int u){
  16. 	color[u]=1;
  17. 	for(auto v: g[u]){
  18. 		if(color[v]==-1){
  19. 			dfs1(v);
  20. 		}
  21. 	}
  22. 	order.push_back(u);
  23. 	color[u]=2;
  24. }
  25. void dfs2(int u){
  26. 	color[u]=1;
  27. 	comp_id[u]=comp_number;
  28. 	fun_sum[comp_number] += fun[u];
  29. 	for(auto v: gr[u]){
  30. 		if(color[v]==-1){
  31. 			dfs2(v);
  32. 		}
  33. 	}
  34. 	color[u]=2;
  35. }
  36. void solve(){
  37. 	fill(all(color),-1);
  38. 	for(int i=1;i<=n;i++){
  39. 		if(color[i]==-1){
  40. 			dfs1(i);
  41. 		}
  42. 	}
  43. 	reverse(all(order));
  44. 	fill(all(color),-1);
  45. 	comp_number=0;
  46. 	for(int i=1;i<=n;i++){
  47. 		if(color[i]==-1){
  48. 			++comp_number;
  49. 			dfs2(i);
  50. 		}
  51. 	}
  52. 	// creating condensation graph
  53. 	for(int i=1;i<=n;i++){
  54. 		gr[i].clear();
  55. 	}
  56. 	for(int u=1;u<=n;u++){
  57. 		for(auto v: g[u]){
  58. 			if(comp_id[v]!=comp_id[u]){
  59. 				gr[comp_id[u]].push_back(comp_id[v]);
  60.  
  61. 			}
  62. 		}
  63. 	}
  64. 	//for(int i=1;i<=comp_number;i++){
  65. 	//	dp[i] = fun_sum[i];
  66. 	//}
  67. 	fill(all(color),-1);
  68. 	queue<int> q;
  69. 	q.push(comp_id[st]);
  70. 	dp[comp_id[st]]=fun_sum[comp_id[st]];
  71. 	while(!q.empty()){
  72. 		int u = q.front();
  73. 		q.pop();
  74. 		color[u]=1;
  75. 		for(auto v: gr[u]){
  76. 			if(color[v]==1)continue;
  77. 			if(dp[v] < (dp[u] + fun_sum[v])){
  78. 				dp[v] = dp[u] + fun_sum[v];
  79. 				q.push(v);
  80. 			}
  81. 		}
  82. 	}
  83. 	cout << dp[comp_id[en]] << endl;
  84. }
  85. signed main(){
  86. 	ios_base::sync_with_stdio(0); 
  87. 	cin.tie(0);
  88. 	cin >> n >> m >> st >> en;
  89. 	for(int i=1;i<=n;i++){
  90. 		cin >> fun[i];
  91. 	}
  92. 	for(int i=1;i<=m;i++){
  93. 		cin >> a >> b;
  94. 		g[a].push_back(b);
  95. 		gr[b].push_back(a);
  96. 	}
  97. 	solve();
  98. 	return 0;
  99. }
Success #stdin #stdout 0.03s 62120KB
comments ()
stdin
copy 
5 6 1 4
5
4
5
10
2
1 2
1 3
2 4
3 4
4 5
5 4
stdout
copy 
22
https://ideone.com/SyrFrp
problem GOODA, based on SPOJ submission 22559297 (CPP14), 2018-10-22 21:03:22
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!