Submission #1691367

---

Source Code Expand

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"
#include "random"

using namespace std;

const long long int MOD = 1000000007;
const long double EPS = 0.00000001;
const long double PI = 3.1415926535897932384626433;

long long int N, M, K, H, W, L, R;

vector<vector<int>>edge;
vector<pair<int,int>>num;
vector<int>value;
bool fin = false;

pair<int, int> Search(int n) {
	if (fin) {
		num[n] = { 0,0 };
		return num[n];
	}
	if (num[n].first != -1) {
		return num[n];
	}
	if (edge[n].empty()) {
		num[n] = { value[n],0 };
		return num[n];
	}
	vector<vector<bool>>flag(edge[n].size() + 1, vector<bool>(value[n] + 1, false));
	flag[0][0] = true;
	int box = 1;
	int sum = 0;
	for (auto i : edge[n]) {
		auto bag = Search(i);
		L = bag.first;
		R = bag.second;
		sum += L;
		sum += R;
		for (int j = value[n]; j >= L; j--) {
			flag[box][j] = flag[box - 1][j - L];
		}
		for (int j = value[n]; j >= R; j--) {
			if (!flag[box][j]) {
				flag[box][j] = flag[box - 1][j - R];
			}
		}
		box++;
	}
	for (int i = value[n]; i >= 0; i--) {
		if (flag[edge[n].size()][i]) {
			//cout << n << " " << i << endl;
			num[n] = { value[n],sum - i };
			return num[n];
		}
	}
	fin = true;
	num[n] = { 0,0 };
	return num[n];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	edge.resize(N + 1);
	num.resize(N + 1, { -1,-1 });
	value.resize(N + 1);
	for (int i = 2; i <= N; i++) {
		cin >> K;
		edge[K].push_back(i);
	}
	for (int i = 1; i <= N; i++) {
		cin >> value[i];
	}
	Search(1);
	if (fin) {
		cout << "IMPOSSIBLE\n";
	}
	else {
		cout << "POSSIBLE\n";
	}
	return 0;
}

Submission Info

Judge Result