Submission #986284

#	Time	Username	Problem	Language	Result	Execution time	Memory
986284		andrei_iorgulescu	File Paths (BOI15_fil)	C++14	33 / 100	68 ms	24604 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];
bool rp[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] = 1;
        else if (kn > 0)
        {
            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 st = a[nod] + s;
        if (k - st >= 0 and rp[k - st])
            ans[nod] = true;
        int tt = t[nod];
        while (tt != 0)
        {
            st += a[tt];
            if (k - st >= 0 and rp[k - st])
                ans[nod] = true;
            tt = t[tt];
        }
    }
}

void dfs0(int nod)
{
    int x = nod;
    int vl = 0;
    while (x != 0)
    {
        vl += a[x];
        x = t[x];
    }
    if (vl <= k)
        rp[vl] = true;
    for (auto fiu : f[nod])
        if (fiu <= n)
            dfs0(fiu);
}

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]++;
    dfs0(0);
    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: 33 / 33
• Subtask 3: 0 / 34