oj.uz

Submission #94114

# Submission time Handle Problem Language Result Execution time Memory
94114 2019-01-16T07:57:13 Z Kastanda File Paths (BOI15_fil) C++11
0 / 100
 1000 ms 86264 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[MXK], 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])
    {
        int kk = k - D[v] - ln[id];
        for (int &d : divv[kk])
            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 < MXK; i++)
        for (int j = i; j < MXK; j += i)
            divv[j].push_back(i);

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

    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:31: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:34: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:38: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 Execution timed out 1072 ms 85096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 86264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 85096 KB Time limit exceeded
2 Halted 0 ms 0 KB -