Submission #94127

#	Time	Username	Problem	Language	Result	Execution time	Memory
94127		Kastanda	File Paths (BOI15_fil)	C++11	100 / 100	190 ms	25928 KiB

fil

#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];

    for (int i = 0; i <= n; i++)
        M[D[i]] = 1;

    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);
            }
    }

    for (int i = 0; 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 (stderr)

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: 33 / 33
• Subtask 2: 33 / 33
• Subtask 3: 34 / 34