oj.uz

Submission #986282

# Submission time Handle Problem Language Result Execution time Memory
986282 2024-05-20T08:39:45 Z andrei_iorgulescu File Paths (BOI15_fil) C++14
0 / 100
 13 ms 4512 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];
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.0

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

Subtask #2
0 / 33.0

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

Subtask #3
0 / 34.0

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