Advertisement
Arrias

Untitled

Jan 7th, 2019
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1000005;
  6. int b[N], sz, vis[N], kk[N];
  7. vector <int> G[N];
  8. unordered_map <int, int> mp;
  9.  
  10. void dfs(int u, int start, bool flag = false) {
  11. if (start == u && flag) {
  12. return;
  13. }
  14. G[sz].push_back(u);
  15. vis[u] = 1;
  16. u = mp[u];
  17. dfs(u, start, 1);
  18. }
  19.  
  20. void fail() {
  21. cout << "No\n";
  22. exit(0);
  23. }
  24.  
  25. void check(int n) {
  26. vector <int> f(n + 1);
  27. bool good = 0;
  28. for (int i = 1; i <= n; ++i)
  29. f[i] = i;
  30. for (int j = 0; j < n + 1; ++j) {
  31. map <int, int> place;
  32. for (int i = 1; i <= n; ++i) {
  33. place[f[i]] = i;
  34. f[i] = mp[f[i]];
  35. }
  36. for (int i = 1; i <= n; ++i)
  37. cout << place[i] << ' ';
  38. cout << "\n";
  39. }
  40. }
  41.  
  42. int main() {
  43. ios::sync_with_stdio(false);
  44. cin.tie(0);
  45. int n; cin >> n;
  46. bool ans = 1;
  47. for (int i = 1; i <= n; ++i) {
  48. int x;
  49. cin >> x;
  50. mp[x] = i;
  51. }
  52. for (int i = 1; i <= n; ++i) {
  53. cin >> b[i];
  54. }
  55. sz = 0;
  56. for (int i = 1; i <= n; ++i) {
  57. if (vis[i] == 0) {
  58. sz++;
  59. G[sz].clear();
  60. dfs(i, i, 0);
  61. }
  62. }
  63. vector <long long> sdvs(sz + 1);
  64. long long T = 0;
  65. long long start = -1;
  66. for (int i = 1; i <= sz; ++i) {
  67. int nz = G[i].size();
  68. vector <int> h(nz);
  69. for (int j = 0; j < nz; ++j) {
  70. h[j] = b[G[i][j]];
  71. }
  72. bool good = 0;
  73. for (int j = 0; j < nz; ++j) {
  74. int s = 0;
  75. int ind = j;
  76. int pi = 0;
  77. while (s < nz && G[i][ind] == h[pi]) {
  78. pi++;
  79. ind++;
  80. ind %= G[i].size();
  81. s++;
  82. }
  83. if (s == nz) {
  84. good = 1, sdvs[i] = j;
  85. if (sdvs[i] == 0)
  86. sdvs[i] = G[i].size();
  87. }
  88. }
  89. if (good == 0) fail();
  90. if (G[i].size() > T) {
  91. T = G[i].size(), start = sdvs[i];
  92. }
  93. }
  94. long long lcm = 1;
  95. for (int i = 1; i <= sz; ++i) {
  96. lcm = (lcm * G[i].size()) / __gcd((long long)G[i].size(), lcm);
  97. }
  98. for (long long t = start; t <= lcm; t += T) {
  99. bool good = 1;
  100. for (int j = 1; j <= sz; ++j) {
  101. if (!(t >= sdvs[j] && (t - sdvs[j]) % G[j].size() == 0))
  102. good = 0;
  103. }
  104. if (good) {
  105. cout << "Yes\n";
  106. exit(0);
  107. }
  108. }
  109. fail();
  110. return 0;
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement