Submission #1128223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128223		stdfloat	File Paths (BOI15_fil)	C++20	0 / 100	128 ms	24244 KiB

fil

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define sz(v)	(int)(v).size()

const int N = (int)3e6 + 1;

int n, X, K, s, tim;

vector<bool> ans;

vector<int> pr, l, tin, tout, cnt1(N), cnt2(N);

vector<vector<int>> E;

void dfs_tm(int x) {
	tin[x] = tim++;
	for (auto i : E[x])
		dfs_tm(i);

	tout[x] = tim++;
}

void dfs(int x) {
	if (n < x) return;

	for (int i = 0; i <= n; i++) {
		if (l[i] < l[x]) continue;
		if (tin[x] <= tin[i] && tout[i] <= tout[x]) cnt1[s + l[i] - l[x]]++;
		else cnt2[s + l[i] - l[x]]++;
	}
	for (int i = n + 1; i <= X; i++) {
		if (tin[x] <= tin[i] && tout[i] <= tout[x]) {
			int y = K - l[i];
			ans[i] = (ans[i] || !y || cnt2[y]);
			for (int j = 1; j * j <= y && !ans[i]; j++)
				if (!(y % j)) ans[i] = (cnt1[j] || cnt1[y / j]);
		}
	}

	for (auto i : E[x])
		dfs(i);

	for (int i = 0; i <= n; i++) {
		if (l[i] < l[x]) continue;
		if (tin[x] <= tin[i] && tout[i] <= tout[x]) cnt1[s + l[i] - l[x]]--;
		else cnt2[s + l[i] - l[x]]--;
	}
}

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

	int m;
	cin >> n >> m >> K >> s; s++;

	X = n + m;
	E.assign(X + 1, {});
	pr = l = vector<int>(X + 1);
	pr[0] = -1;
	for (int i = 1; i <= X; i++) {
		cin >> pr[i] >> l[i];

		l[i] += 1 + l[pr[i]];
		E[pr[i]].push_back(i);
	}

	tin = tout = vector<int>(X + 1);
	dfs_tm(0);

	ans.assign(X + 1, false);
	dfs(0);

	for (int i = n + 1; i <= X; i++)
		cout << (ans[i] ? "YES" : "NO") << '\n';
}

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