Advertisement
Guest User

Untitled

a guest
Oct 12th, 2018
199
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None
  1. /*
  2.  ID: bradyawn
  3.  PROG: contest
  4.  LANG: C++11
  5.  */
  6.  
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <iomanip>
  10. #include <fstream>
  11. #include <vector>
  12. #include <deque>
  13. #include <string>
  14. #include <cmath>
  15. #include <map>
  16. #include <unordered_map>
  17. #include <utility>
  18. #include <set>
  19. #include <unordered_set>
  20. #include <ctime>
  21. #include <queue>
  22. #include <stack>
  23. #include <bitset>
  24. #include <random>
  25. #include <cstring>
  26. #include <complex>
  27. #include <cassert>
  28.  
  29. using namespace std;
  30.  
  31. typedef long long ll;
  32. typedef long double ld;
  33. typedef pair<int,int> i2;
  34. typedef pair<ll,ll> ll2;
  35.  
  36. ll n, L, S;
  37.  
  38. int w[100001];
  39. int p[100001];
  40. int d[100001];
  41. bool vis[100001];
  42. vector<int> at[100001];
  43.  
  44. int ret = 0;
  45.  
  46. void solve(int cur)
  47. {
  48.     if (vis[cur]) return;
  49.     ret++;
  50.     ll weight = S;
  51.     int cnt = L;
  52.     while (weight-w[cur] >= 0 && cnt-1 >= 0 && cur)
  53.     {
  54.         weight -= w[cur];
  55.         cnt--;
  56.         vis[cur] = 1;
  57.         cur = p[cur];
  58.     }
  59. //    solve(cur);
  60. }
  61.  
  62. int main()
  63. {
  64.     //ifstream inf("");
  65.     //ofstream outf("");
  66.     cout << setprecision(10);
  67.     ios::sync_with_stdio(0); cin.tie(0);
  68.    
  69.     cin >> n >> L >> S; //mxlen, mxsum
  70.    
  71.     for (int i = 1; i <= n; i++)
  72.     {
  73.         cin >> w[i];
  74.         if (w[i] > S)
  75.         {
  76.             cout << -1 << '\n';
  77.             return 0;
  78.         }
  79.     }
  80.     for (int i = 2; i <= n; i++)
  81.     {
  82.         cin >> p[i];
  83.         d[i] = d[p[i]]+1;
  84.         at[d[i]].push_back(i);
  85.     } at[0].push_back(1);
  86.    
  87.     for (int dep = n; dep >= 0; dep--)
  88.         for (auto e : at[dep]) solve(e);
  89.    
  90.     cout << ret << '\n';
  91.    
  92.     return 0;
  93. }
Advertisement
RAW Paste Data Copied
Advertisement