fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. static const ll INF = (1LL<<60);
  6.  
  7. int main() {
  8.     ios::sync_with_stdio(false);
  9.     cin.tie(nullptr);
  10.  
  11.     int t;
  12.     cin >> t;
  13.     while (t--) {
  14.         ll n, k;
  15.         int PB, PS;
  16.         cin >> n >> k >> PB >> PS;
  17.         PB--; 
  18.         PS--;  // convert to 0-based indices
  19.  
  20.         vector<int> perm(n);
  21.         for (int i = 0; i < n; i++) {
  22.             cin >> perm[i];
  23.             perm[i]--;  // make it 0-based
  24.         }
  25.         vector<ll> arr(n);
  26.         for (int i = 0; i < n; i++) {
  27.             cin >> arr[i];
  28.         }
  29.  
  30.         auto best_score = [&](int s) -> ll {
  31.             // 1) Find path and detect cycle
  32.             vector<int> pos(n, -1), path;
  33.             path.reserve(n);
  34.             int cur = s;
  35.             while (pos[cur] == -1) {
  36.                 pos[cur] = (int)path.size();
  37.                 path.push_back(cur);
  38.                 cur = perm[cur];
  39.             }
  40.             int t0 = pos[cur];            // index in path where cycle starts
  41.             int L  = (int)path.size() - t0;  // cycle length
  42.  
  43.             // 2) Build prefix sums over the entire path
  44.             vector<ll> pre(path.size() + 1, 0LL);
  45.             for (int i = 0; i < (int)path.size(); i++) {
  46.                 pre[i+1] = pre[i] + arr[ path[i] ];
  47.             }
  48.  
  49.             // 3) Extract cycle values from path[t0 .. end-1]
  50.             vector<ll> cycVals(L), cycPre(L+1, 0LL);
  51.             ll maxC = 0;
  52.             for (int i = 0; i < L; i++) {
  53.                 cycVals[i] = arr[ path[t0 + i] ];
  54.                 cycPre[i+1] = cycPre[i] + cycVals[i];
  55.                 maxC = max(maxC, cycVals[i]);
  56.             }
  57.  
  58.             // 4) If k < t0, we never enter the cycle; we can only walk k steps.
  59.             if (k < t0) {
  60.                 // At turn 0, position = path[0]; at turn 1, path[1], ... up to turn k = path[k].
  61.                 return pre[k+1];
  62.             }
  63.  
  64.             // 5) Otherwise, we walk the entire tail of length t0 first.
  65.             ll sumTail = pre[t0];
  66.  
  67.             // 6) We have (k - t0) turns left to move around the cycle (or stay).
  68.             ll ans = 0;
  69.             ll left = k - t0;
  70.  
  71.             // Try walking j steps into the cycle (0 <= j < L), then stay at cycle-max
  72.             for (int j = 0; j < L; j++) {
  73.                 if ((ll)j > left) break;
  74.                 // sumTail + sum of the first (j+1) cycle‐nodes + (left - j) * maxC
  75.                 ll cand = sumTail + cycPre[j+1] + (left - j) * maxC;
  76.                 ans = max(ans, cand);
  77.             }
  78.             return ans;
  79.         };
  80.  
  81.         ll sb = best_score(PB);
  82.         ll ss = best_score(PS);
  83.         if (sb > ss) {
  84.             cout << "Bodya\n";
  85.         } else if (ss > sb) {
  86.             cout << "Sasha\n";
  87.         } else {
  88.             cout << "Draw\n";
  89.         }
  90.     }
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
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
copy 
Bodya
Sasha
Draw
Draw
Bodya
Sasha
Sasha
Bodya
Sasha
Bodya
https://ideone.com/QPVGlM
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

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!