Submission #949390

#	Time	Username	Problem	Language	Result	Execution time	Memory
949390		Ghulam_Junaid	File Paths (BOI15_fil)	C++17	0 / 100	66 ms	127060 KiB

fil

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

typedef long long ll;

const ll N = 505;
const ll K = 1e6 + 5;

ll n, m, k, s, p[N], len[N], ans[N];
ll total[N];
vector<pair<ll, ll>> query[N];
vector<ll> g[N];
bitset<K> B[N];

void dfs(ll v){
    for (ll u : g[v]){
        if (u == p[v]) continue;
        B[u] = (B[v] << (len[u] + 1));
        B[u] |= B[v];
        total[u] = total[v] + (len[u] + 1);
        dfs(u);
    }

    for (auto [l, id] : query[v]){
        ll cur = total[v] + l + 1;
        ll down = cur + s + 1 - k;

        // cout << "at v = " << v << " with len = " << l << endl;
        // cout << "cur = " << cur << " down = " << down << endl;

        if (cur < k){
            ll rem = k - cur;
            for (ll d = 1; d * d <= rem; d ++){
                if (rem % d) continue;
                ll X = d - (s + 1);
                if (X >= 0 and B[v][X])
                    ans[id] = 1;
                
                X = (rem / d) - (s + 1);
                if (X >= 0 and B[v][X])
                    ans[id] = 1;
            }
        }

        if (cur == k)
            ans[id] = 1;

        if (ans[id] or down < 0)
            continue;

        ll tmp = v;
        set<ll> st;
        while (tmp != 0){
            st.insert(total[tmp]);
            tmp = p[tmp];
            if (st.find(down + total[tmp]) != st.end()){
                ans[id] = 1;
                break;
            }
        }
    }
}

int main(){
    cin >> n >> m >> k >> s;
    len[0] = 1;
    for (ll i = 1; i <= n; i ++){
        cin >> p[i] >> len[i];
        g[p[i]].push_back(i);
    }

    for (ll i = 0; i < m; i ++){
        ll par, l;
        cin >> par >> l;

        query[par].push_back({l, i});

        // ll total = l + 1;

        // ll v = par;
        // while (v != 0){
        //     total += len[v] + 1;
        //     v = p[v];
        // }

        // cout << total << endl;

        // ll rem = k - total;
        // v = par;
        // bool ans = (rem % (s + 1)) == 0;
        // while (v != 0){
        //     if (rem % (s + len[v] + 2) == 0)
        //         ans = 1;
        //     v = p[v];
        // }

        // if (ans)
        //     cout << "YES" << endl;
        // else
        //     cout << "NO" << endl;
    }

    B[0][0] = 1;
    dfs(0);

    for (ll i = 0; i < m; i ++)
        cout << (ans[i] ? "YES" : "NO") << endl;
}

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