fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <stack>
  5. using namespace std;
  6. typedef long long ll;
  7. #define SZ(a) (int)(a).size()
  8.  
  9. const int nil = -1;
  10. const int oo = 0x3f3f3f3f;
  11.  
  12. vector<vector<int>> al;
  13. vector<int> low;
  14. stack<int> t;
  15. vector<vector<int>> sccs;
  16.  
  17. void genSCC(int u) {
  18. 	auto d = SZ(t);
  19. 	low[u] = d;
  20. 	t.push(u);
  21. 	for (auto v: al[u]) {
  22. 		if (low[v] == nil) genSCC(v);
  23. 		low[u] = min(low[u], low[v]);
  24. 	}
  25. 	if (low[u] == d) {
  26. 		vector<int> scc;
  27. 		int top;
  28. 		do {
  29. 			top = t.top();
  30. 			t.pop();
  31. 			low[top] = oo;
  32. 			scc.push_back(top);
  33. 		} while (top != u);
  34. 		sccs.push_back(scc);
  35. 	}
  36. }
  37.  
  38. int main() {
  39. 	cin.sync_with_stdio(false);
  40. 	int n, m;
  41. 	cin >> n >> m;
  42. 	vector<int> cs(n);
  43. 	for (int i = 0; i < n; i++) {
  44. 		cin >> cs[i];
  45. 	}
  46. 	al.assign(n, {});
  47. 	for (int i = 0; i < m; i++) {
  48. 		int u, v;
  49. 		cin >> u >> v;
  50. 		u--, v--;
  51. 		al[u].push_back(v);
  52. 	}
  53. 	low.assign(n, nil);
  54. 	for (int u = 0; u < n; u++) {
  55. 		if (low[u] == nil) genSCC(u);
  56. 	}
  57. 	int nscc = SZ(sccs);
  58. 	vector<int> isccs(n);
  59. 	for (int i = 0; i < nscc; i++) {
  60. 		for (auto u: sccs[i]) {
  61. 			isccs[u] = i;
  62. 		}
  63. 	}
  64. 	vector<vector<int>> aldag(SZ(sccs));
  65. 	for (int i = 0; i < nscc; i++) {
  66. 		for (auto u: sccs[i]) {
  67. 			for (auto v: al[u]) {
  68. 				aldag[i].push_back(isccs[v]);
  69. 			}
  70. 		}
  71. 	}
  72. 	vector<ll> ans(nscc, 0);
  73. 	for (int i = 0; i < nscc; i++) {
  74. 		for (auto j: aldag[i]) {
  75. 			ans[i] = max(ans[i], ans[j]);
  76. 		}
  77. 		for (auto u: sccs[i]) {
  78. 			ans[i] += cs[u];
  79. 		}
  80. 	}
  81. 	for (int u = 0; u < n; u++) {
  82. 		printf("%lld%c", ans[isccs[u]], " \n"[u == n-1]);
  83. 	}
  84. }
  85.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0 0 0 0 0 0 0
https://ideone.com/XCvTjy
language:
C++14 (gcc 8.3)
created:
7 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!