Submission #986282

#	Time	Username	Problem	Language	Result	Execution time	Memory
986282		andrei_iorgulescu	File Paths (BOI15_fil)	C++14	0 / 100	13 ms	4512 KiB

fil

#include <bits/stdc++.h>

using namespace std;

int n,m,k,s;
int t[6005],a[6005];
vector<int> f[6005];
int fr[1000005];
int ans[6005];

void dfs(int nod)
{
    vector<int> bg;
    if (nod <= n)
    {
        int x = nod;
        int sm = 0;
        fr[0]++;
        bg.push_back(0);
        while (x != 0)
        {
            sm += a[x];
            if (sm <= k)
                fr[sm]++,bg.push_back(sm);
            x = t[x];
        }
        for (auto fiu : f[nod])
            dfs(fiu);
        for (auto it : bg)
            fr[it]--;
    }
    else
    {
        int x = nod;
        int sm = a[nod];
        while (x != 0)
        {
            x = t[x];
            sm += a[x];
        }
        int kn = k - sm;
        if (kn < 0)
            ans[nod] = 0;
        else if (kn == 0)
            ans[nod] = 1;
        else
        {
            for (int d = 1; d * d <= kn; d++)
            {
                if (kn % d == 0)
                {
                    int knn;
                    knn = kn / d - s;
                    if (knn >= 0 and fr[knn])
                        ans[nod] = 1;
                    knn = d - s;
                    if (knn >= 0 and fr[knn])
                        ans[nod] = 1;
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m >> k >> s;
    s++;
    for (int i = 1; i <= n + m; i++)
        cin >> t[i] >> a[i],f[t[i]].push_back(i),a[i]++;
    dfs(0);
    for (int i = n + 1; i <= n + m; i++)
    {
        if (ans[i] == 0)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
    return 0;
}

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