fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. int main() {
  6. ios::sync_with_stdio(false);
  7. cin.tie(nullptr);
  8.  
  9. int t;
  10. cin >> t;
  11. while (t--) {
  12. ll n, k;
  13. int p1, p2;
  14. cin >> n >> k >> p1 >> p2;
  15. p1--;
  16. p2--;
  17. vector<int> perm(n + 1);
  18. vector<ll> arr(n + 1);
  19.  
  20. for (int i = 1; i <= n; i++) {
  21. cin >> perm[i];
  22. }
  23. for (int i = 1 ; i <= n; i ++) {
  24. cin >> arr[i];
  25. }
  26.  
  27. ll p1max = 0, p2max = 0;
  28. ll p1sum = 0, p2sum = 0;
  29. ll steps = min<ll>(k, n);
  30. int cur1 = p1, cur2 = p2;
  31.  
  32. for (int i = 0; i < steps; i++) {
  33. // Add the “chain contribution” from staying at cur1 for (k - i) more steps:
  34. p1max = max(p1max, p1sum + (k - i) * arr[cur1]);
  35. // Then walk to the next in the cycle:
  36. p1sum += perm[cur1];
  37. cur1 = perm[cur1];
  38.  
  39. p2max = max(p2max, p2sum + (k - i) * arr[cur2]);
  40. p2sum += arr[cur2];
  41. cur2 = perm[cur2];
  42. }
  43.  
  44. if (p1max > p2max) {
  45. cout << "Bodya\n";
  46. } else if (p2max > p1max) {
  47. cout << "Sasha\n";
  48. } else {
  49. cout << "Draw\n";
  50. }
  51. }
  52. return 0;
  53. }
  54.  
Success #stdin #stdout 0.01s 5276KB
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
Sasha
Sasha
Sasha
Bodya
Draw
Bodya
Bodya
Bodya
Bodya
Sasha