oj.uz

Submission #94115

# Submission time Handle Problem Language Result Execution time Memory
94115 2019-01-16T08:00:22 Z Kastanda File Paths (BOI15_fil) C++11
33 / 100
 159 ms 25020 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 3009, MXK = 1000006;
int n, m, k, slen, P[N], L[N], D[N];
int pd[N], ln[N];
bool res[N];
int cnt[MXK];
bitset < MXK > M;
vector < int > divv[N], Q[N], A[N], Adj[N];
void DFS(int v)
{
    for (int &a : A[v])
        cnt[a] ++;

    for (int &u : Adj[v])
        DFS(u);

    for (int &id : Q[v])
    {
        for (int &d : divv[id])
            if (cnt[d])
                res[id] = 1;
    }

    for (int &a : A[v])
        cnt[a] --;
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &slen); slen ++;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &P[i], &L[i]);
        L[i] ++; Adj[P[i]].push_back(i);
    }
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &pd[i], &ln[i]), ln[i] ++;
    for (int i = 1; i <= n; i++)
        D[i] = D[P[i]] + L[i], M[D[i]] = 1;
    M[D[0]] = 1; // Corner case

    for (int i = 1; i <= m; i++)
    {
        // D[?] + slen + D[v] - D[p] + ln[i] == k
        int v = pd[i], p = v;
        while (N)
        {
            int len = slen + D[v] - D[p] + ln[i];
            if (len <= k && M[k - len])
                res[i] = 1;
            if (p == 0)
                break;
            p = P[p];
        }
        if (D[pd[i]] + ln[i] == k)
            res[i] = 1;
    }

    for (int i = 1; i <= m; i++)
    {
        Q[pd[i]].push_back(i);

        int kk = k - D[pd[i]] - ln[i];
        for (int d = 1; d * d <= kk; d ++)
            if (kk % d == 0)
            {
                divv[i].push_back(d);
                divv[i].push_back(kk / d);
            }
    }

    M = 0;
    for (int i = 1; i <= n; i++)
    {
        int p = i;
        while (N)
        {
            int len = D[i] - D[p] + slen;
            if (len < MXK)
                A[p].push_back(len);
            if (p == 0)
                break;
            p = P[p];
        }
    }
    DFS(0);

    for (int i = 1; i <= m; i++)
        puts(res[i] ? "YES" : "NO");
    return 0;
}

Compilation message

fil.cpp: In function 'int main()':
fil.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &m, &k, &slen); slen ++;
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &P[i], &L[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fil.cpp:37:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &pd[i], &ln[i]), ln[i] ++;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 5 ms 1656 KB Output is correct
5 Correct 7 ms 4600 KB Output is correct
6 Correct 7 ms 3320 KB Output is correct
7 Correct 9 ms 4856 KB Output is correct
8 Correct 6 ms 3960 KB Output is correct
9 Correct 5 ms 4088 KB Output is correct
10 Incorrect 2 ms 760 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4856 KB Output is correct
2 Correct 11 ms 4856 KB Output is correct
3 Correct 11 ms 4984 KB Output is correct
4 Correct 12 ms 5116 KB Output is correct
5 Correct 157 ms 24540 KB Output is correct
6 Correct 159 ms 25020 KB Output is correct
7 Correct 87 ms 15864 KB Output is correct
8 Correct 103 ms 16228 KB Output is correct
9 Correct 12 ms 4600 KB Output is correct
10 Correct 11 ms 4088 KB Output is correct
11 Correct 7 ms 1784 KB Output is correct
12 Correct 149 ms 21752 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 5 ms 1656 KB Output is correct
5 Correct 7 ms 4600 KB Output is correct
6 Correct 7 ms 3320 KB Output is correct
7 Correct 9 ms 4856 KB Output is correct
8 Correct 6 ms 3960 KB Output is correct
9 Correct 5 ms 4088 KB Output is correct
10 Incorrect 2 ms 760 KB Output isn't correct
11 Halted 0 ms 0 KB -