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.  
  9. ll calc(int x, int n, int k) {
  10. if (k == 0) {
  11. return 0;
  12. }
  13. if (k == 1) return a[x];
  14. if (x == p[x]) return 1ll * k * a[x];
  15. int step = 1;
  16. ll val, path_sum;
  17. val = path_sum = a[x];
  18. while (step < min(n, k)) {
  19. if (val * (step + 1) <= path_sum + a[p[x]]) {
  20. return path_sum + calc(p[x], n, k - step);
  21. } else {
  22. path_sum += a[p[x]];
  23. x = p[x];
  24. }
  25. step++;
  26. }
  27. return val * k;
  28. }
  29.  
  30. void solve() {
  31. int n, k, B, S;
  32. cin >> n >> k >> B >> S;
  33. B--; S--;
  34. for (int i = 0; i < n; i++) {
  35. cin >> p[i];
  36. p[i]--;
  37. }
  38. for (int i = 0; i < n; i++) cin >> a[i];
  39.  
  40. ll b_score = calc(B, n, k);
  41. ll s_score = calc(S, n, k);
  42.  
  43. if (b_score > s_score) {
  44. cout << "Bodya" << endl;
  45. } else if (b_score < s_score) {
  46. cout << "Sasha" << endl;
  47. }
  48. else cout << "Draw" << endl;
  49. }
  50.  
  51. int main() {
  52. int t;
  53. cin >> t;
  54. while (t--) solve();
  55. }
Success #stdin #stdout 0.01s 5296KB
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
Draw
Bodya
Sasha
Sasha
Sasha
Sasha
Bodya