Submission #705364

#	Time	Username	Problem	Language	Result	Execution time	Memory
705364		LittleCube	File Paths (BOI15_fil)	C++14	0 / 100	9 ms	4436 KiB

fil

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int n, m, k, s, dep[6006], occ[2000006], l[6006], ans[6006];
vector<int> E[6006], cur;

void dfs(int u)
{
    if (u <= n)
    {
        cur.emplace_back(u);
        for (auto p : cur)
            occ[dep[u] - dep[p] + s]++;
        for (auto v : E[u])
        {
            dep[v] = dep[u] + l[v];
            dfs(v);
        }
        for (auto p : cur)
            occ[dep[u] - dep[p] + s]--;
        cur.pop_back();
    }
    else
    {
        ans[u] = (dep[u] == k);
        for (int i = 1; i * i <= k - dep[u]; i++)
            if((k - dep[u]) % i == 0)
            {
                int j = (k - dep[u]) / i;
                ans[u] |= (occ[i] || occ[j]);
            }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k >> s;
    s++;
    for (int i = 1; i <= n + m; i++)
    {
        int p;
        cin >> p >> l[i];
        l[i]++;
        E[p].emplace_back(i);
    }
    dfs(0);
    for (int i = n + 1; i <= n + m; i++)
        cout << (ans[i] ? "YES\n" : "NO\n");
}

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