Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ID: bradyawn
- PROG: contest
- LANG: C++11
- */
- #include <iostream>
- #include <algorithm>
- #include <iomanip>
- #include <fstream>
- #include <vector>
- #include <deque>
- #include <string>
- #include <cmath>
- #include <map>
- #include <unordered_map>
- #include <utility>
- #include <set>
- #include <unordered_set>
- #include <ctime>
- #include <queue>
- #include <stack>
- #include <bitset>
- #include <random>
- #include <cstring>
- #include <complex>
- #include <cassert>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int,int> i2;
- typedef pair<ll,ll> ll2;
- ll n, L, S;
- int w[100001];
- int p[100001];
- int d[100001];
- bool vis[100001];
- vector<int> at[100001];
- int ret = 0;
- void solve(int cur)
- {
- if (vis[cur]) return;
- ret++;
- ll weight = S;
- int cnt = L;
- while (weight-w[cur] >= 0 && cnt-1 >= 0 && cur)
- {
- weight -= w[cur];
- cnt--;
- vis[cur] = 1;
- cur = p[cur];
- }
- // solve(cur);
- }
- int main()
- {
- //ifstream inf("");
- //ofstream outf("");
- cout << setprecision(10);
- ios::sync_with_stdio(0); cin.tie(0);
- cin >> n >> L >> S; //mxlen, mxsum
- for (int i = 1; i <= n; i++)
- {
- cin >> w[i];
- if (w[i] > S)
- {
- cout << -1 << '\n';
- return 0;
- }
- }
- for (int i = 2; i <= n; i++)
- {
- cin >> p[i];
- d[i] = d[p[i]]+1;
- at[d[i]].push_back(i);
- } at[0].push_back(1);
- for (int dep = n; dep >= 0; dep--)
- for (auto e : at[dep]) solve(e);
- cout << ret << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement