Submission #564368

#	Time	Username	Problem	Language	Result	Execution time	Memory
564368		KoD	File Paths (BOI15_fil)	C++17	100 / 100	98 ms	29740 KiB

fil

#include <bits/stdc++.h>

using std::vector;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M, K, S;
    std::cin >> N >> M >> K >> S;
    K -= 1, S += 1;
    vector<int> parent(N + M + 1), depth(N + M + 1);
    vector<vector<int>> children(N + 1);
    for (int i = 1; i <= N; ++i) {
        int p, l;
        std::cin >> p >> l;
        parent[i] = p;
        depth[i] = depth[p] + l + 1;
        children[p].push_back(i);
    }
    for (int i = N + 1; i <= N + M; ++i) {
        int p, l;
        std::cin >> p >> l;
        parent[i] = p;
        depth[i] = depth[p] + l;
        children[p].push_back(i);
    }
    vector<char> exists(K + 1);
    vector<vector<int>> list(N + 1);
    for (int i = 0; i <= N; ++i) {
        exists[depth[i]] = true;
        for (int j = i; j != 0;) {
            j = parent[j];
            const int len = depth[i] - depth[j] + S;
            if (len <= K) {
                list[j].push_back(len);
            }
        }
    }
    vector<char> ans(M);
    vector<int> anc, count(K + 1);
    auto dfs = [&](auto&& dfs, const int u) -> void {
        if (u > N) {
            ans[u - (N + 1)] = [&] {
                const int goal = K - depth[u];
                if (goal % S == 0) {
                    return true;
                }
                for (const int v : anc) {
                    const int shortcut = goal - S + depth[v];
                    if (shortcut >= 0 and exists[shortcut]) {
                        return true;
                    }
                }
                for (int d = 1; d * d <= goal; ++d) {
                    if (goal % d == 0) {
                        if (count[d] > 0 or count[goal / d] > 0) {
                            return true;
                        }
                    }
                }
                return false;
            }();
        } else {
            anc.push_back(u);
            for (const int x : list[u]) {
                count[x] += 1;
            }
            for (const int v : children[u]) {
                dfs(dfs, v);
            }
            anc.pop_back();
            for (const int x : list[u]) {
                count[x] -= 1;
            }
        }
    };
    dfs(dfs, 0);
    for (const char c : ans) {
        std::cout << (c ? "YES" : "NO") << '\n';
    }
    return 0;
}

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