Submission #1227096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227096		kaiboy	File Paths (BOI15_fil)	C++20	0 / 100	2 ms	1604 KiB

fil

#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 dd[N];
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_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, s_, w_; cin >> n >> k >> s_ >> w_, n++, w_++;
	for (int i = 1; i < n; i++) {
		int p, w; cin >> p >> w, w++;
		ejw[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_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_ || used[s_ - w_ - d])
				good[h] = true;
		}
	for (int h = 0; h < k; h++)
		cout << (good[h] ? "YES" : "NO") << '\n';
	return 0;
}

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