Submission #1227711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227711		kaiboy	File Paths (BOI15_fil)	C++20	100 / 100	159 ms	45436 KiB

fil

// coached by rainboy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int  N = 3001;
const int N_ = 3000;
const int  S = 1000000;

vector<pair<int, int>> ejw[N], qu[N];
int pp[N], dd[N], kk[S + 1], s_, w_;
bool used[S + 1], good[N_];

void dfs_dd(int i, int d) {
	used[dd[i] = d] = true;
	for (auto &jw : ejw[i]) {
		int j = jw.first, w = jw.second;
		dfs_dd(j, d + w);
	}
}

void dfs_kk(int i, int s, int k) {
	if (s + w_ <= s_)
		kk[s + w_] += k;
	for (auto &jw : ejw[i]) {
		int j = jw.first, w = jw.second;
		dfs_kk(j, s + w, k);
	}
}

void dfs_good(int i) {
	dfs_kk(i, 0, 1);
	for (auto &hd : qu[i]) {
		int h = hd.first, d = hd.second;
		int s = s_ - dd[i] - d;
		for (int e = 1; e <= s / e; e++)
			if (s % e == 0 && (kk[e] || kk[s / e])) {
				good[h] = true;
				break;
			}
	}
	for (auto &jw : ejw[i])
		dfs_good(jw.first);
	dfs_kk(i, 0, -1);
}

void dfs_qu(int i) {
	for (auto &jw : ejw[i]) {
		int j = jw.first, w = jw.second;
		dfs_qu(j);
		for (auto &hd : qu[j]) {
			int h = hd.first, d = hd.second;
			qu[i].push_back({ h, w + d });
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, k; cin >> n >> k >> s_ >> w_, n++, w_++;
	pp[0] = -1;
	for (int i = 1; i < n; i++) {
		int p, w; cin >> p >> w, w++;
		ejw[pp[i] = p].push_back({ i, w });
	}
	for (int h = 0; h < k; h++) {
		int i, d; cin >> i >> d, d++;
		qu[i].push_back({ h, d });
	}
	dfs_dd(0, 0);
	dfs_good(0);
	dfs_qu(0);
	for (int i = 0; i < n; i++)
		for (auto &hd : qu[i]) {
			int h = hd.first, d = hd.second;
			if (dd[i] + d == s_ || s_ >= w_ + d && used[s_ - w_ - d])
				good[h] = true;
		}
	for (int h = 0; h < k; h++)
		cout << (good[h] ? "YES" : "NO") << '\n';
	return 0;
}

• Subtask 1: 33 / 33
• Subtask 2: 33 / 33
• Subtask 3: 34 / 34