fork download 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. // #define int long long
  6. #define fi first
  7. #define se second
  8. #define siz(x) (int)(x.size())
  9. #define all(x) x.begin(), x.end()
  10. #define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
  11. #define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
  12. const int maxN = 5e4+5;
  13.  
  14. int n, m, q, a[maxN], ans[maxN];
  15. vector<int>adj[maxN];
  16. multiset<int>s[maxN];
  17.  
  18. void dfs(int u, int v)
  19. {
  20. 	for(auto i: adj[u])
  21. 	{
  22. 		if(i == v) continue;
  23. 		dfs(i,u);
  24. 		if(siz(s[u]) < siz(s[i])) swap(s[u], s[i]);
  25. 		for(auto j: s[i])
  26. 		{
  27. 			s[u].insert(j);
  28. 			auto tmp = s[u].find(j);
  29. 			tmp++;
  30. 			auto xet = s[u].begin(); xet--;
  31. 			if(tmp != s[u].end()) ans[u] = min(ans[u], *tmp - j);
  32. 			tmp--;
  33. 			if(tmp == s[u].begin()) continue;
  34. 			tmp--;
  35. 			if(tmp != s[u].end())
  36. 			{
  37. 			 	ans[u] = min(ans[u], j - *tmp);
  38. 			}
  39. 		}
  40. 		ans[u] = min(ans[u], ans[i]);
  41. 	}
  42. }
  43.  
  44. void solve()
  45. {
  46.  
  47. }
  48.  
  49. int32_t main()
  50. {
  51. 	ios_base::sync_with_stdio(0); cin.tie(0);
  52. 	cin>>n>>m;
  53. 	for(int i=1; i<=n; i+=1) ans[i] = (1ll<<31) - 1;
  54. 	for(int i=2; i<=n; i+=1)
  55. 	{
  56. 		int x; cin>>x;
  57. 		adj[x].push_back(i);
  58. 		adj[i].push_back(x);
  59. 	}
  60. 	for(int i=n-m+1; i<=n; i+=1) cin>>a[i];
  61. 	for(int i=n-m+1; i<=n; i+=1) s[i].insert(a[i]);
  62. 	dfs(1, 0);
  63. 	for(int i=1; i<=n-m; i+=1)
  64. 	{
  65. 		cout<<ans[i]<<' ';
  66. 	}
  67. }
Success #stdin #stdout 0.01s 6992KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/v19xws
language:
C++14 (gcc 8.3)
created:
11 days 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!