Submission #986287

#	Time	Username	Problem	Language	Result	Execution time	Memory
986287		andrei_iorgulescu	File Paths (BOI15_fil)	C++14	100 / 100	79 ms	51828 KiB

fil

#include <bits/stdc++.h>

using namespace std;

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

void dfs(int nod)
{
    vector<int> bg;
    if (nod <= n)
    {
        ///pentru fiecare u din subtree[nod] pot face un drum de sp[u] - sp[nod] + s de multe ori, deci vreau sa marchez sp[u] - sp[nod]
        for (auto u : subtree[nod])
            if (sp[u] - sp[nod] <= k)
                bg.push_back(sp[u] - sp[nod]);
        for (auto it : bg)
            fr[it]++;//cout << it << endl;
        for (auto fiu : f[nod])
            dfs(fiu);
        for (auto it : bg)
            fr[it]--;//cout << -it << endl;
    }
    else
    {
        int x = nod;
        int sm = 0;
        while (x != 0)
        {
            sm += a[x];
            x = t[x];
        }
        int kn = k - sm;
        //cout << "? " << kn << endl;
        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] = 1;
        int tt = t[nod];
        while (tt != 0)
        {
            st += a[tt];
            if (k - st >= 0 and rp[k - st])
                ans[nod] = 1;
            tt = t[tt];
        }
    }
}

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

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: 33 / 33
• Subtask 2: 33 / 33
• Subtask 3: 34 / 34