oj.uz

Submission #986284

# Submission time Handle Problem Language Result Execution time Memory
986284 2024-05-20T08:48:11 Z andrei_iorgulescu File Paths (BOI15_fil) C++14
33 / 100
 68 ms 24604 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5464 KB Output is correct
2 Correct 9 ms 5468 KB Output is correct
3 Correct 9 ms 5464 KB Output is correct
4 Correct 9 ms 5468 KB Output is correct
5 Correct 68 ms 22408 KB Output is correct
6 Correct 66 ms 22352 KB Output is correct
7 Correct 44 ms 10408 KB Output is correct
8 Correct 43 ms 10244 KB Output is correct
9 Correct 10 ms 5468 KB Output is correct
10 Correct 8 ms 5468 KB Output is correct
11 Correct 5 ms 2652 KB Output is correct
12 Correct 61 ms 24604 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -