제출 #218259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218259		dolphingarlic	File Paths (BOI15_fil)	C++14	100 / 100	184 ms	8064 KiB

fil

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m, k, s;
vector<int> graph[6060];
int to_root[6060], par[6060], can[2020202], cyc[2020202];
bool good[6060];

void add_cycles(int node, int root, int val) {
	cyc[to_root[node] - to_root[root] + s] += val;
	for (int i : graph[node]) if (i <= n) add_cycles(i, root, val);
}

void dfs(int node = 0) {
	if (node > n) {
		int add_dist = k - to_root[node];
		if (!add_dist) good[node] = true;
		for (int i = 1; i * i <= add_dist; i++)
			if (add_dist % i == 0 && (cyc[i] || cyc[add_dist / i])) good[node] = true;
		for (int i = par[node]; ~i; i = par[i])
			if (add_dist - s + to_root[i] >= 0 && can[add_dist - s + to_root[i]]) good[node] = true;
	}
	add_cycles(node, node, 1);
	for (int i : graph[node]) dfs(i);
	add_cycles(node, node, -1);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k >> s;
	s++;
	par[0] = -1;
	can[0] = 1;
	FOR(i, 1, n + m + 1) {
		int l;
		cin >> par[i] >> l;
		graph[par[i]].push_back(i);
		to_root[i] = to_root[par[i]] + l + 1;
		if (i <= n) can[to_root[i]]++;
	}
	dfs();

	FOR(i, n + 1, n + m + 1) cout << (good[i] ? "YES\n" : "NO\n");
	return 0;
}

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