Submission #890999

#	Time	Username	Problem	Language	Result	Execution time	Memory
890999		shiomusubi496	File Paths (BOI15_fil)	C++17	100 / 100	239 ms	40356 KiB

fil

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define all(v) begin(v), end(v)

using ll = long long;

struct edge {
    int to;
    ll cost;
    edge(int t, ll c) : to(t), cost(c) {}
};

int main() {
    int n, m, k, s; cin >> n >> m >> k >> s;
    ++n;
    vector<vector<edge>> g(n);
    vector<int> par(n, -1);
    ++s;
    rep2 (i, 1, n) {
        int p, l; cin >> p >> l;
        g[p].emplace_back(i, l + 1);
        par[i] = p;
    }
    vector<ll> d(n);
    vector<vector<ll>> ch(n);
    {
        auto dfs = [&](auto&& self, int v) -> vector<ll> {
            vector<ll> res;
            for (auto e : g[v]) {
                d[e.to] = d[v] + e.cost;
                for (auto i : self(self, e.to)) res.push_back(i + e.cost);
            }
            res.push_back(0);
            return ch[v] = res;
        };
        dfs(dfs, 0);
    }
    set<int> exist;
    rep (i, n) {
        if (d[i] <= 3 * k) exist.insert(d[i]);
    }
    vector<vector<pair<int, int>>> qs(n);
    vector<bool> ans(m, false);
    rep (i, m) {
        int p, l; cin >> p >> l;
        int t = k - l - 1;
        if (d[p] == t) ans[i] = true;
        else {
            t -= d[p];
            qs[p].emplace_back(i, t);
            for (int j = p; j != -1; j = par[j]) {
                if (exist.count(t + d[j] - s) != 0) ans[i] = true;
            }
        }
    }
    {
        vector<int> cnt(k + 1);
        auto dfs = [&](auto&& self, int v) -> void {
            for (auto i : ch[v]) {
                if (i <= k) ++cnt[i];
            }
            for (auto [i, t] : qs[v]) {
                for (ll j = 1; j * j <= t; ++j) {
                    if (t % j != 0) continue;
                    if (s <= j && cnt[j - s] > 0) ans[i] = true;
                    if (s <= t / j && cnt[t / j - s] > 0) ans[i] = true;
                }
            }
            for (auto e : g[v]) self(self, e.to);
            for (auto i : ch[v]) {
                if (i <= k) --cnt[i];
            }
        };
        dfs(dfs, 0);
    }
    for (auto i : ans) puts(i ? "YES" : "NO");
}

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