fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int N = 2e5 + 5;
  7. int p[N], a[N];
  8. bool vis[N];
  9.  
  10. ll calc(int x, int n, int k) {
  11. if (k == 0) {
  12. return 0;
  13. }
  14. vis[x] = true;
  15. if (k == 1) return a[x];
  16. if (x == p[x]) return 1ll * k * a[x];
  17. int step = 1;
  18. ll val, path_sum;
  19. val = path_sum = a[x];
  20. while (step < min(n, k)) {
  21. if (vis[p[x]]) {
  22. return path_sum + (k - step) * a[x];
  23. }
  24. if (val * (step + 1) <= path_sum + a[p[x]]) {
  25. return path_sum + calc(p[x], n, k - step);
  26. } else {
  27. path_sum += a[p[x]];
  28. x = p[x];
  29. vis[x] = true;
  30. }
  31. step++;
  32. }
  33. return val * k;
  34. }
  35.  
  36. void solve() {
  37. int n, k, B, S;
  38. cin >> n >> k >> B >> S;
  39. B--; S--;
  40. for (int i = 0; i < n; i++) {
  41. cin >> p[i];
  42. p[i]--;
  43. }
  44. for (int i = 0; i < n; i++) cin >> a[i];
  45.  
  46. memset(vis, false, n);
  47. ll b_score = calc(B, n, k);
  48. memset(vis, false, n);
  49. ll s_score = calc(S, n, k);
  50.  
  51. if (b_score > s_score) {
  52. cout << "Bodya" << endl;
  53. } else if (b_score < s_score) {
  54. cout << "Sasha" << endl;
  55. }
  56. else cout << "Draw" << endl;
  57. }
  58.  
  59. int main() {
  60. int t;
  61. cin >> t;
  62. while (t--) solve();
  63. }
Success #stdin #stdout 0.01s 5288KB
stdin
10
4 2 3 2
4 1 2 3
7 2 5 6
10 8 2 10
3 1 4 5 2 7 8 10 6 9
5 10 5 1 3 7 10 15 4 3
2 1000000000 1 2
1 2
4 4
8 10 4 1
5 1 4 3 2 8 6 7
1 1 2 1 2 100 101 102
5 1 2 5
1 2 4 5 3
4 6 9 4 2
4 2 3 1
4 1 3 2
6 8 5 3
6 9 5 4
6 1 3 5 2 4
6 9 8 9 5 10
4 8 4 2
2 3 4 1
5 2 8 7
4 2 3 1
4 1 3 2
6 8 5 3
2 1000000000 1 2
1 2
1000000000 2
stdout
Bodya
Sasha
Draw
Bodya
Bodya
Sasha
Sasha
Bodya
Sasha
Bodya