fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int maxn = 5005;
  5. vector<int> g[maxn], ed[maxn];
  6. int n, k, dp[maxn][maxn], num[maxn], low[maxn], sccid[maxn], scc, par[maxn], sz[maxn], v[maxn], indegree[maxn], sccv[maxn], tplt, t;
  7. vector<int> id;
  8. stack<int> st;
  9. bool vis[maxn];
  10. struct node{
  11. 	int id, sz, v;
  12. };
  13. vector<node> a;
  14. void dfs(int u, int p)
  15. {
  16. 	vis[u] = 1;
  17. 	low[u] = num[u] = ++t;
  18. 	st.push(u);
  19. 	for(int v : g[u])
  20. 	{
  21. 		if(v == p) continue;
  22. 		if(num[v]) low[u] = min(low[u], num[v]);
  23. 		else
  24. 		{
  25. 			dfs(v, u);
  26. 			low[u] = min(low[u], low[v]);
  27. 		}
  28. 	}
  29. 	if(low[u] == num[u])
  30. 	{
  31. 		scc++;
  32. 		while(st.top() != u)
  33. 		{
  34. 			int v = st.top();
  35. 			st.pop();
  36. 			sccid[v] = scc;
  37. 		}
  38. 		int v = st.top();
  39. 		st.pop();
  40. 		sccid[v] = scc;
  41. 	}
  42. }
  43. void dfs2(int u)
  44. {
  45. 	for(int v : ed[u])
  46. 	{
  47. 		dfs2(v);
  48. 		sccv[u] += sccv[v];
  49. 		sz[u] += sz[v];
  50. 	}
  51. 	a.push_back({tplt, sz[u], sccv[u]});
  52. }
  53. int32_t main()
  54. {
  55. 	ios_base::sync_with_stdio(0);
  56. 	cin.tie(0);
  57. 	if(fopen("actnet.inp", "r"))
  58. 	{
  59. 		freopen("actnet.inp", "r", stdin);
  60. 		freopen("actnet.out", "w", stdout);
  61. 	}
  62. 	cin >> n >> k;
  63. 	for(int i = 1; i <= n; i++)
  64. 	{
  65. 		cin >> par[i];
  66. 		if(par[i] != i) 
  67. 		{
  68. 			g[i].push_back(par[i]);
  69. 			g[par[i]].push_back(i);
  70. 		}
  71. 	}
  72. 	for(int i = 1; i <= n; i++) cin >> v[i];
  73. 	for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i, i);
  74. // 	cout << sccid[5] << ' ' << sccid[6] << '\n';
  75. 	for(int i = 1; i <= n; i++)
  76. 	{
  77. 	   // if(par[i] == i) indegree[sccid[i]]++;
  78. 		if(sccid[par[i]] != sccid[i])
  79. 		{
  80. 		    ed[sccid[i]].push_back(sccid[par[i]]);
  81. // 			ed[sccid[par[i]]].push_back(sccid[i]);
  82. 			indegree[sccid[par[i]]]++;
  83. 		}
  84. 		sccv[sccid[i]] += v[i];
  85. 		sz[sccid[i]]++;
  86. 	}
  87. // 	cout << indegree[3] << '\n';
  88. 	for(int i = 1; i <= scc; i++)
  89. 	{
  90. 		if(indegree[i] == 0)
  91. 		{
  92. 			tplt++;
  93. 			dfs2(i);
  94. 		}
  95. 	}
  96. 	int last = 0, ans = 0;
  97. 	dp[1][a[0].sz] = a[0].v;
  98. 	for(int i = 2; i <= a.size(); i++)
  99. 	{
  100. 		for(int j = 0; j <= k; j++)
  101. 		{
  102. 			dp[i][j] = dp[i - 1][j];
  103. 		}
  104. 		if(a[i - 1].id != a[i - 2].id) last = i - 1;
  105. 		for(int j = 0; j <= k; j++)
  106. 		{
  107. 			if(j + a[i - 1].sz <= k) dp[i][j + a[i - 1].sz] = max(dp[i][j + a[i - 1].sz], dp[last][j] + a[i - 1].v);
  108. 			ans = max(ans, dp[i][j]);
  109. 		}
  110. 	}
  111. // 	for(node x : a) cout << x.id << ' ' << x.sz << ' ' << x.v << '\n';
  112. 	cout << ans;
  113. 	return 0;
  114. }
Success #stdin #stdout 0.01s 5356KB
comments (?)
stdin 
6 4
2 3 1 2 6 6
10 20 15 40 50 5
stdout 
85
https://ideone.com/4CAVUn
language:
C++ (gcc 8.3)
created:
7 hours 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!