fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std; 
  4.  
  5. typedef long long ll; 
  6. typedef pair<int, int> ii; 
  7.  
  8. const ll LINF = 1e18; 
  9. const int INF = 1e9;
  10.  
  11. // - Đây là một bài tuy không khó nhưng đòi hỏi các em phải nháp và vẽ vời ra một tí để thấy
  12. // - Gọi a(k)(i) là giá trị của phần tử nằm ở vị trí thứ i sau k thao tác biến đổi
  13. // - Ta có a(k)(i) = a(k - 1)(x(i)) = a(k - 2)(x(x(i))) = a(k - 3)(x(x(x(i)))) = ... = a(0)(x(...x(...x(i)))) (*)
  14. // - Từ đây ta dựng đồ thị có các cạnh nối i -> x(i), đây là dạng đồ thị có tính chất đặc biệt: mỗi đỉnh chỉ có đúng một cung đi ra (functional graph)
  15. // - Dựa vào tính chất đó ta có thể áp dụng Binary Lifting để giải 
  16. // - Dãy biến đổi (*) chỉ đơn giản là ta xuất phát ở đỉnh i và nhảy k bước thì sẽ đến được đỉnh nào?
  17.  
  18. const int N = 2e5 + 5; 
  19. const int LOG = 60; 
  20.  
  21. int n; ll k;  
  22. int x[N]; 
  23. int a[N]; 
  24. int nxt[LOG][N]; // nxt[i][u]: là đỉnh mà ta đến được nếu xuất phát từ đỉnh u và nhảy 2^i bước
  25.  
  26. void precompute() {
  27. 	for (int u = 1; u <= n; u++) nxt[0][u] = x[u]; 
  28.  
  29. 	for (int i = 1; i < LOG; i++) {
  30. 		for (int u = 1; u <= n; u++) {
  31. 			nxt[i][u] = nxt[i - 1][nxt[i - 1][u]]; 
  32. 		}
  33. 	}
  34. }
  35.  
  36. // int jump_brute(int u, int k) {
  37. 	// for (int i = 1; i <= k; i++) u = x[u]; 
  38. 	// return u; 
  39. // }
  40.  
  41. // Đỉnh mà ta đến được nếu xuất phát từ đỉnh u và nhảy k bước
  42. int jump(int u, ll k) {
  43. 	for (int i = 0; i < LOG; i++) {
  44. 		if ((k >> i) & 1) {
  45. 			u = nxt[i][u]; 
  46. 		}
  47. 	}
  48. 	return u; 
  49. }
  50.  
  51. int ans[N]; 
  52.  
  53. signed main() {
  54. 	ios::sync_with_stdio(false); 
  55. 	cin.tie(nullptr); 	
  56. 	cin >> n >> k; 
  57. 	for (int i = 1; i <= n; i++) cin >> x[i];  
  58. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  59.  
  60. 	precompute(); 	
  61.  
  62. 	for (int i = 1; i <= n; i++) {
  63. 		ans[i] = a[jump(i, k)]; 
  64. 	}
  65.  
  66. 	for (int i = 1; i <= n; i++) cout << ans[i] << ' '; 
  67. }
Success #stdin #stdout 0.01s 50588KB
comments (?)
stdin
copy 
7 3
5 2 6 3 1 4 6
1 2 3 5 7 9 11
stdout
copy 
7 2 3 5 1 9 3
https://ideone.com/491UMU
language:
C++14 (gcc 8.3)
created:
148 days 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!