fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. const int INF = int(1e9);
  25. struct SCC
  26. {
  27. 	vector<vector<int> > vec;
  28. 	int index;
  29. 	vector<int> idx;
  30. 	vector<int> lowlink;
  31. 	vector<bool> onstack;
  32. 	stack<int> s;
  33. 	vector<int> sccidx;
  34. 	int scccnt;
  35. 	//lower sccidx means appear later
  36. 	void init(int n)
  37. 	{
  38. 		idx.assign(n,-1);
  39. 		index = 0;
  40. 		onstack.assign(n,0);
  41. 		lowlink.assign(n,INF);
  42. 		while(!s.empty()) s.pop();
  43. 		sccidx.assign(n,-1);
  44. 		scccnt = 0;
  45. 		vec.clear();
  46. 		vec.resize(n);
  47. 	}
  48.  
  49. 	void addedge(int u, int v) //u -> v
  50. 	{
  51. 		vec[u].pb(v);
  52. 	}
  53.  
  54. 	void connect(int u)
  55. 	{
  56. 		idx[u] = index;
  57. 		lowlink[u] = index;
  58. 		index++;
  59. 		s.push(u);
  60. 		onstack[u] = true;
  61. 		for(int i = 0; i < vec[u].size(); i++)
  62. 		{
  63. 			int v = vec[u][i];
  64. 			if(idx[v] == -1)
  65. 			{
  66. 				connect(v);
  67. 				lowlink[u] = min(lowlink[u], lowlink[v]);
  68. 			}
  69. 			else if(onstack[v])
  70. 			{
  71. 				lowlink[u] = min(lowlink[u], idx[v]);
  72. 			}
  73. 		}
  74. 		if(lowlink[u] == idx[u])
  75. 		{
  76. 			while(1)
  77. 			{
  78. 				int v = s.top();
  79. 				s.pop();
  80. 				onstack[v] = false;
  81. 				sccidx[v] = scccnt;
  82. 				if(v == u) break;
  83. 			}
  84. 			scccnt++;
  85. 		}
  86. 	}
  87.  
  88. 	void tarjan()
  89. 	{
  90. 		for(int i = 0; i < vec.size(); i++)
  91. 		{
  92. 			if(idx[i] == -1)
  93. 			{
  94. 				connect(i);
  95. 			}
  96. 		}
  97. 	}
  98. };
  99.  
  100. SCC scc;
  101.  
  102. const int N = 300000;
  103. ll cnt[300001];
  104. ll dp[300001];
  105. vi adj[300001];
  106. vector<ii> edges;
  107. int main()
  108. {
  109. 	ios_base::sync_with_stdio(0); cin.tie(0);
  110. 	int n, m; cin>>n>>m;
  111. 	scc.init(n);
  112. 	for(int i = 0; i < n; i++)
  113. 	{
  114. 		cin>>cnt[i];
  115. 	}
  116. 	for(int i = 0; i < m; i++)
  117. 	{
  118. 		int u, v;
  119. 		cin>>u>>v;
  120. 		u--; v--;
  121. 		edges.pb(mp(u,v));
  122. 		scc.addedge(u,v);
  123. 	}	
  124. 	scc.tarjan();
  125. 	int maxidx = 0;
  126. 	for(int i = 0; i < n; i++)
  127. 	{
  128. 		dp[scc.sccidx[i]] += cnt[i];
  129. 		maxidx = max(maxidx, scc.sccidx[i]);
  130. 	}
  131. 	for(int i = 0; i < m; i++)
  132. 	{
  133. 		int l = scc.sccidx[edges[i].fi];
  134. 		int r = scc.sccidx[edges[i].se];
  135. 		if(l==r) continue;
  136. 		adj[l].pb(r);
  137. 		assert(l>r);
  138. 	}
  139. 	//larger sccidx -> lower sccidx
  140. 	for(int i = 0; i <= maxidx; i++)
  141. 	{
  142. 		ll cnt = dp[i];
  143. 		for(int j = 0; j < adj[i].size(); j++)
  144. 		{
  145. 			int u = adj[i][j];
  146. 			dp[i] = max(cnt+dp[u], dp[i]);
  147. 		}
  148. 	}
  149. 	for(int i = 0; i < n; i++)
  150. 	{
  151. 		cout << dp[scc.sccidx[i]] << ' ';
  152. 	}
  153. }
  154.  
Runtime error #stdin #stdout #stderr 0s 27792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:137: int main(): Assertion `l>r' failed.
https://ideone.com/vj1YDe
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!