Submission #1270658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270658		BuzzyBeez	File Paths (BOI15_fil)	C++20	100 / 100	329 ms	92464 KiB

fil

#include <bits/allocator.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h> 
using namespace std;

vector<int> divisors(long long n) {
	vector<int> res;
	if (n <= 0) return res;
	for (int i = 1; i * i <= n; ++i) if (n % i == 0) {
		res.push_back(i);
		if (i * i < n) res.push_back(n / i);
	}
	return res;
}

const int N = 1e6;

int s, k;
int id_D[3008], id_F[3008];
int f[N + 8];
vector<pair<int, int>> adj[6008];
long long d[6008];
vector<int> anc[6008], des[6008];
bool stop[6008], ans[6008];

void DFS_prep(int u) {
	if (u > 1) anc[u].push_back(u);
	if (!stop[u]) des[u].push_back(u);
	for (pair<int, int> edge : adj[u]) {
		// cout << u << ' ' << edge.first << endl;
		d[edge.first] = d[u] + edge.second;
		anc[edge.first] = anc[u];
		DFS_prep(edge.first);
		for (int i : des[edge.first]) des[u].push_back(i);
	}
}

void modify(int u, int c) {
	if (u == 1) return;
	for (int v : des[u]) if (0 < d[v] - d[u] + s && d[v] - d[u] + s <= N)
		f[d[v] - d[u] + s] += c;
}

void solve(int u) {
	if (k == d[u]) {
		ans[u] = 1; 
		// cout << u << ' ' << d[u] << "!!" << endl;
		return;
	}
	// cout << u << ' ' << d[u] << "!!" << endl;
	// cout << ">> ";
	// for (int i : anc[u]) cout << i << ' ';
	// cout << endl;
	for (int d : divisors(k - d[u])) ans[u] |= (f[d] > 0);
}

void DFS(int u) {
	modify(u, +1); int v;
	for (pair<int, int> edge : adj[u]) {
		v = edge.first;
		if (stop[v]) solve(v);
		else DFS(v);
	}
	modify(u, -1);
}

map<long long, int> mp;
void solve_simple_case(int u) {
	// d[v1] + s + d[u] - d[v2] = k <=> exist v1 :: d[v1] = k - d[u] + d[a (in anc[u])] - s
	if (ans[u]) return;
	long long t;
	for (int a : anc[u]) if (a != u) {
		t = k - d[u] + d[a] - s;
		if (mp[t]) {
			ans[u] = 1;
			return;
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, p, len; cin >> n >> m >> k >> s; ++s;
	int buff = 2; adj[1].emplace_back(2, 1);
	for (int i = 1; i <= n; ++i) {
		cin >> p >> len; 
		++len; p += buff;
		adj[p].emplace_back(i + buff, len);
	}
	for (int i = n + 1; i <= n + m; ++i) {
		cin >> p >> len;
		p += buff;
		adj[p].emplace_back(i + buff, len);
		stop[i + buff] = 1;
	}
	DFS_prep(1); 
	DFS(1);
	
	for (int i = 2; i <= n + buff; ++i) mp[d[i]] = 1;
	for (int i = n + 1; i <= n + m; ++i) solve_simple_case(i + buff);
	
	for (int i = n + 1; i <= n + m; ++i) cout << (ans[i + buff] ? "YES\n" : "NO\n");
}

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