oj.uz

Submission #104629

# Submission time Handle Problem Language Result Execution time Memory
104629 2019-04-08T12:50:58 Z teomrn File Paths (BOI15_fil) C++14
100 / 100
 202 ms 28344 KB 
#include <stdio.h>
#include <vector>
#include <set>
#include <assert.h>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

const int NMAX = 6010;
int f_ap[NMAX], l_ap[NMAX], cnt;
int h[NMAX];
int l_link; /// lungimea linkului
vector <pair <int, int>> adia[NMAX];
int father[NMAX];
vector <int> l_cycles[NMAX];
int n, m, k;
/// sunt n foldere, m fisiere, vreau lungimea finala sa fie fix k
bool ok[NMAX];
int length[NMAX];
int global[2000010], active[2000010];

bool is_son(int father, int son)
{
    return f_ap[father] <= f_ap[son] && l_ap[father] >= l_ap[son];
}

void dfs(int nod)
{
    f_ap[nod] = ++cnt;

    for (auto i : adia[nod]) {
        h[i.first] = h[nod] + i.second;
        father[i.first] = nod;
        dfs(i.first);
    }

    l_ap[nod] = ++cnt;
}

void calc_rec(int nod)
{
    if (nod > n) {
        /// este un fisier

        if (h[nod] == k) {
            ok[nod] = 1;
            return;
        }

        for (int i = father[nod]; i != -1; i = father[i]) {
            int dif = h[nod] - h[i];
            dif = k - dif;

            if (global[dif]) {
                ok[nod] = 1;
                return;
            }
        }

        int dif = k - h[nod];

        for (int l = 1; l * l <= dif; l++) {
            if (dif % l == 0) {
                if (active[l] || active[dif / l]) {
                    ok[nod] = 1;
                    return;
                }
            }
        }
        return;
    }

    for (auto i : l_cycles[nod])
        active[i]++;

    for (auto i : adia[nod])
        calc_rec(i.first);

    for (auto i : l_cycles[nod]) {
        active[i]--;
    }
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &l_link);
    l_link++;
    father[0] = -1;

    for (int i = 1; i <= n + m; i++) {
        int father, l;
        scanf("%d%d", &father, &l);
        l++;
        length[i] = l;
        adia[father].push_back({ i, l });
    }

    dfs(0);

    for (int i = 0; i <= n; i++) {
        /// fac un syslink aici
        /// -> o sa am lungimea totala pana acum h[i] + l_link
        global[h[i] + l_link]++;

        for (int j = 0; j <= i; j++) {
            if (!is_son(j, i))
                continue;
            /// fac un syslink de la i la j
            int made = h[i] - h[j] + l_link;
            l_cycles[j].push_back(made);
        }
    }

    calc_rec(0);

    for (int i = n + 1; i <= n + m; i++) {
        if (ok[i])
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;
}

Compilation message

fil.cpp: In function 'int main()':
fil.cpp:87: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, &l_link);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &father, &l);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 4 ms 1408 KB Output is correct
4 Correct 5 ms 1792 KB Output is correct
5 Correct 9 ms 5632 KB Output is correct
6 Correct 7 ms 4096 KB Output is correct
7 Correct 14 ms 7168 KB Output is correct
8 Correct 7 ms 5376 KB Output is correct
9 Correct 8 ms 5376 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 4 ms 1664 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7808 KB Output is correct
2 Correct 25 ms 8000 KB Output is correct
3 Correct 21 ms 7808 KB Output is correct
4 Correct 24 ms 7936 KB Output is correct
5 Correct 197 ms 27972 KB Output is correct
6 Correct 185 ms 27896 KB Output is correct
7 Correct 111 ms 18360 KB Output is correct
8 Correct 114 ms 18440 KB Output is correct
9 Correct 25 ms 7808 KB Output is correct
10 Correct 29 ms 7524 KB Output is correct
11 Correct 21 ms 1684 KB Output is correct
12 Correct 157 ms 22836 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 4 ms 1408 KB Output is correct
4 Correct 5 ms 1792 KB Output is correct
5 Correct 9 ms 5632 KB Output is correct
6 Correct 7 ms 4096 KB Output is correct
7 Correct 14 ms 7168 KB Output is correct
8 Correct 7 ms 5376 KB Output is correct
9 Correct 8 ms 5376 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 4 ms 1664 KB Output is correct
13 Correct 22 ms 7808 KB Output is correct
14 Correct 25 ms 8000 KB Output is correct
15 Correct 21 ms 7808 KB Output is correct
16 Correct 24 ms 7936 KB Output is correct
17 Correct 197 ms 27972 KB Output is correct
18 Correct 185 ms 27896 KB Output is correct
19 Correct 111 ms 18360 KB Output is correct
20 Correct 114 ms 18440 KB Output is correct
21 Correct 25 ms 7808 KB Output is correct
22 Correct 29 ms 7524 KB Output is correct
23 Correct 21 ms 1684 KB Output is correct
24 Correct 157 ms 22836 KB Output is correct
25 Correct 23 ms 7984 KB Output is correct
26 Correct 26 ms 7864 KB Output is correct
27 Correct 23 ms 7900 KB Output is correct
28 Correct 21 ms 7936 KB Output is correct
29 Correct 202 ms 28152 KB Output is correct
30 Correct 190 ms 28344 KB Output is correct
31 Correct 109 ms 18424 KB Output is correct
32 Correct 111 ms 18040 KB Output is correct
33 Correct 25 ms 7544 KB Output is correct
34 Correct 27 ms 7476 KB Output is correct
35 Correct 19 ms 1664 KB Output is correct
36 Correct 184 ms 26488 KB Output is correct