fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2e5 + 5;
  5. vector<int> graph[N];
  6. vector<int> a;
  7. vector<bool> vis(N);
  8. long long mx = 0;
  9.  
  10. void dfs(int node,int k, long long sum){
  11.     if(k == 0){
  12.         return;
  13.     }
  14.     vis[node] = true;
  15.     // try to stop at that node
  16.     mx = max(mx, sum + k * a[node]);
  17.     for(auto child: graph[node]){
  18.         if(!vis[child]){
  19.             // try to take that node with us
  20.             dfs(child, k - 1, sum + a[node]);
  21.         }
  22.     }
  23. }
  24. void solve(){
  25.     int n, x, k, pb, ps;
  26.     cin >> n >> k >> pb >> ps;
  27.     for(int i = 1; i <= n; i++){
  28.         cin >> x;
  29.         graph[i].push_back(x);
  30.     }
  31.     a.resize(n + 1);
  32.     vis.resize(n + 1, false);
  33.     for(int i = 1 ;i <= n; i++){
  34.         cin >> a[i];
  35.     }
  36.  
  37.     dfs(pb, k, 0);
  38.     long long mxb = mx;
  39.     mx = 0;
  40.  
  41.     dfs(ps, k, 0);
  42.     long long mxs = mx;
  43.  
  44.     if(mxs == mxb){
  45.         cout << "Draw\n";
  46.     }
  47.     else if(mxs > mxb){
  48.         cout << "Sasha\n";
  49.     }
  50.     else {
  51.         cout << "Bodya\n";
  52.     }
  53.     for(int i = 1; i <= n;i++){
  54.         graph[i].clear();
  55.     }
  56.  
  57. }
  58. int main()
  59. {
  60.     int t;
  61.     cin >> t;
  62.     while(t--){
  63.         solve();
  64.  
  65.         // get ready for next iteration
  66.         vis.clear();
  67.         a.clear();
  68.         mx = 0;
  69.     }
  70.  
  71. }
  72.  
Success #stdin #stdout 0.01s 8204KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Szp7Cy
language:
C++ (gcc 8.3)
created:
11 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!