oj.uz

Submission #986287

# Submission time Handle Problem Language Result Execution time Memory
986287 2024-05-20T09:01:16 Z andrei_iorgulescu File Paths (BOI15_fil) C++14
100 / 100
 79 ms 51828 KB 
#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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 3 ms 3576 KB Output is correct
5 Correct 4 ms 5724 KB Output is correct
6 Correct 4 ms 5468 KB Output is correct
7 Correct 5 ms 6744 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 2 ms 5468 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 3 ms 3676 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5720 KB Output is correct
2 Correct 9 ms 5856 KB Output is correct
3 Correct 10 ms 5724 KB Output is correct
4 Correct 9 ms 5724 KB Output is correct
5 Correct 74 ms 44828 KB Output is correct
6 Correct 75 ms 44728 KB Output is correct
7 Correct 47 ms 21852 KB Output is correct
8 Correct 47 ms 21848 KB Output is correct
9 Correct 10 ms 5904 KB Output is correct
10 Correct 9 ms 5720 KB Output is correct
11 Correct 5 ms 3672 KB Output is correct
12 Correct 66 ms 43600 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 3 ms 3576 KB Output is correct
5 Correct 4 ms 5724 KB Output is correct
6 Correct 4 ms 5468 KB Output is correct
7 Correct 5 ms 6744 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 2 ms 5468 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 3 ms 3676 KB Output is correct
13 Correct 9 ms 5720 KB Output is correct
14 Correct 9 ms 5856 KB Output is correct
15 Correct 10 ms 5724 KB Output is correct
16 Correct 9 ms 5724 KB Output is correct
17 Correct 74 ms 44828 KB Output is correct
18 Correct 75 ms 44728 KB Output is correct
19 Correct 47 ms 21852 KB Output is correct
20 Correct 47 ms 21848 KB Output is correct
21 Correct 10 ms 5904 KB Output is correct
22 Correct 9 ms 5720 KB Output is correct
23 Correct 5 ms 3672 KB Output is correct
24 Correct 66 ms 43600 KB Output is correct
25 Correct 9 ms 5720 KB Output is correct
26 Correct 9 ms 5744 KB Output is correct
27 Correct 9 ms 6196 KB Output is correct
28 Correct 9 ms 5724 KB Output is correct
29 Correct 74 ms 44724 KB Output is correct
30 Correct 78 ms 45296 KB Output is correct
31 Correct 54 ms 22172 KB Output is correct
32 Correct 51 ms 21836 KB Output is correct
33 Correct 8 ms 5720 KB Output is correct
34 Correct 7 ms 5976 KB Output is correct
35 Correct 6 ms 3676 KB Output is correct
36 Correct 79 ms 51828 KB Output is correct