Submission #44652

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44652	2018-04-04T10:34:25 Z	RayaBurong25_1	File Paths (BOI15_fil)	C++17	0 / 100	975 ms	109716 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 Pa[3005], Sum[3005];
void dfs(int u, int pa, int sum)
{
    // printf("dfs %d %d %d\n", u, pa, sum);
    int i, j, v, s = AdjList[u].size();
    Pa[u] = 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);
            for (j = 0; j < QS[v].size(); j++)
                QS[u].push_back(QS[v][j]);
        }
    }
}
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);
    // kk = 0;
    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
        {
            F[i] = F[r];
            for (kk = 0; kk < F[r].size(); 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());
        }
        // if (F[i].size() > kk)
            // kk = F[i].size();
        // printf("%d = %d\n", i, F[i].size());
    }
    // printf("%d\n", kk);
    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, -1, 0);
    for (i = 0; i <= n; i++)
    {
        // printf("%d: ", i);
        std::sort(QS[i].begin(), QS[i].end());
        // for (j = 0; j < QS[i].size(); j++)
            // printf("%d ", QS[i][j]);
        // printf("\n");
    }
    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;
        }
        while (pa != -1)
        {
            for (j = 0; j < F[kk].size(); j++)
            {
                r = kk/F[kk][j] - s;
                if (r < 0) break;
                if (F[kk][j] == 1)
                {
                    //special case
                    q = std::lower_bound(QS[0].begin(), QS[0].end(), Sum[pa] + r) - QS[0].begin();
                    if (q < QS[0].size() && QS[0][q] == Sum[pa] + r)
                    {
                        printf("YES\n");
                        mark = 1;
                        break;
                    }
                }
                // printf("r%d\n", r);
                q = std::lower_bound(QS[pa].begin(), QS[pa].end(), Sum[pa] + r) - QS[pa].begin();
                if (q < QS[pa].size() && QS[pa][q] == Sum[pa] + r)
                {
                    printf("YES\n");
                    mark = 1;
                    break;
                }
            }
            if (mark)
                break;
            pa = Pa[pa];
        }
        if (!mark)
            printf("NO\n");
    }
}

Compilation message

fil.cpp: In function 'void dfs(int, int, int)':
fil.cpp:25:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < QS[v].size(); j++)
                         ~~^~~~~~~~~~~~~~
fil.cpp: In function 'int main()':
fil.cpp:58:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (kk = 0; kk < F[r].size(); kk++)
                          ~~~^~~~~~~~~~~~~
fil.cpp:104:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < F[kk].size(); j++)
                         ~~^~~~~~~~~~~~~~
fil.cpp:112:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if (q < QS[0].size() && QS[0][q] == Sum[pa] + r)
                         ~~^~~~~~~~~~~~~~
fil.cpp:121:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (q < QS[pa].size() && QS[pa][q] == Sum[pa] + r)
                     ~~^~~~~~~~~~~~~~~
fil.cpp:89:12: warning: unused variable 'p' [-Wunused-variable]
     int l, p, q;
            ^
fil.cpp:34: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:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &s);
     ~~~~~^~~~~~~~~~
fil.cpp:76: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:93: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	23928 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 33.0

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

Subtask #3

0 / 34.0

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