제출 #1227108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227108		kaiboy	File Paths (BOI15_fil)	C++20	33 / 100	30 ms	50504 KiB

fil

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

pair<int, int> ejw[N][N], qu[N][N];
int eo[N], cnt[N];
int pp[N], dd[N];
bool used[S + 1], good[N_];

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

void dfs_qu(int i) {
	for (int o = 0; o < eo[i]; o++) {
		auto jw = ejw[i][o];
		int j = jw.first, w = jw.second;
		dfs_qu(j);
		for (int z = 0; z < cnt[j]; z++) {
			auto hd = qu[j][z];
			int h = hd.first, d = hd.second;
			qu[i][cnt[i]++] = { 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_++;
	pp[0] = -1;
	for (int i = 1; i < n; i++) {
		int p, w; cin >> p >> w, w++;
		ejw[pp[i] = p][eo[p]++] = { i, w };
	}
	for (int h = 0; h < k; h++) {
		int i, d; cin >> i >> d, d++;
		qu[i][cnt[i]++] = { h, d };
	}
	dfs_dd(0, 0);
	dfs_qu(0);
	for (int i = 0; i < n; i++)
		for (int z = 0; z < cnt[i]; z++) {
			auto hd = qu[i][z];
			int h = hd.first, d = hd.second;
			if (dd[i] + d == s_ || s_ >= w_ + d && used[s_ - w_ - d])
				good[h] = true;
			else if (n <= 501 && k <= 500 && s_ >= dd[i] + d)
				for (int p = i; p >= 0; p = pp[p]) {
					int s = dd[i] + d, d_ = w_ + dd[i] - dd[p];
					if ((s_ - s) % d_ == 0) {
						good[h] = true;
						break;
					}
				}
		}
	for (int h = 0; h < k; h++)
		cout << (good[h] ? "YES" : "NO") << '\n';
	return 0;
}

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