Submission #44647

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44647	2018-04-04T09:45:36 Z	RayaBurong25_1	File Paths (BOI15_fil)	C++17	0 / 100	1000 ms	122124 KB

fil

#include <stdio.h>
#include <vector>
#include <algorithm>
typedef struct edge edge;
struct edge
{
    int v, w;
};
std::vector<edge> AdjList[3005];
std::vector<int> QS[3005];
int Sum[3005];
void dfs(int u, int pa, int sum)
{
    // printf("dfs %d %d %d\n", u, pa, sum);
    int i, v, s = AdjList[u].size();
    QS[u] = QS[pa];
    QS[u].push_back(sum);
    Sum[u] = sum;
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i].v;
        if (v != pa)
            dfs(v, u, sum + AdjList[u][i].w);
    }
}
std::vector<int> F[1000005];
int main()
{
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    k--;
    int i, j, r, kk;
    F[1].push_back(1);
    for (i = 2; i <= k; i++)
    {
        r = i;
        for (j = 2; j*j <= i; j++)
        {
            if (i%j == 0)
            {
                r /= j;
                break;
            }
        }
        if (j*j > i)
        {
            F[i].push_back(1);
            F[i].push_back(i);
        }
        else
        {
            for (kk = 0; kk < F[r].size(); kk++)
            {
                F[i].push_back(F[r][kk]);
                F[i].push_back(F[r][kk]*j);
            }
            std::sort(F[i].begin(), F[i].end());
            F[i].resize(std::unique(F[i].begin(), F[i].end()) - F[i].begin());
        }
        // printf("%d = %d\n", i, F[i].size());
    }
    int s;
    scanf("%d", &s);
    s++;
    int pa, w;
    for (i = 1; i <= n; i++)
    {
        scanf("%d %d", &pa, &w);
        AdjList[i].push_back({pa, w + 1});
        AdjList[pa].push_back({i, w + 1});
    }
    dfs(0, 0, 0);
    int l, p, q;
    int mark;
    for (i = 0; i < m; i++)
    {
        scanf("%d %d", &pa, &l);
        kk = k - l - Sum[pa];
        mark = 0;
        // printf("kk%d\n", kk);
        if (kk == 0)
        {
            printf("YES\n");
            continue;
        }
        for (j = 0; j < F[kk].size(); j++)
        {
            r = kk/F[kk][j] - s;
            if (r < 0) break;
            // printf("r%d\n", r);
            for (p = QS[pa].size() - 1; QS[pa][p] >= r; p--)
            {
                q = std::lower_bound(QS[pa].begin(), QS[pa].end(), r - QS[pa][p]) - QS[pa].begin();
                if (QS[pa][q] == r - QS[pa][p])
                {
                    printf("YES\n");
                    mark = 1;
                    break;
                }
            }
            if (mark)
                break;
        }
        if (!mark)
            printf("NO\n");
    }
}

Compilation message

fil.cpp: In function 'int main()':
fil.cpp:52:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (kk = 0; kk < F[r].size(); kk++)
                          ~~~^~~~~~~~~~~~~
fil.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < F[kk].size(); j++)
                     ~~^~~~~~~~~~~~~~
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", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fil.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &s);
     ~~~~~^~~~~~~~~~
fil.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &pa, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~
fil.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &pa, &l);
         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1

0 / 33.0

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

Subtask #2

0 / 33.0

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

Subtask #3

0 / 34.0

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