oj.uz

Submission #104623

# Submission time Handle Problem Language Result Execution time Memory
104623 2019-04-08T12:35:38 Z teomrn File Paths (BOI15_fil) C++14
0 / 100
 1000 ms 62584 KB 
#include <stdio.h>
#include <vector>
#include <set>
#include <assert.h>
#include <vector>
using namespace std;

const int NMAX = 6010;
int f_ap[NMAX], l_ap[NMAX], cnt;
int h[NMAX];
int l_link; /// lungimea linkului
set <int> global_path;
multiset <int> active;
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];

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

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

            if (global_path.find(dif) != global_path.end()) {
                ok[nod] = 1;
                return;
            }
        }

        int dif = k - h[nod];

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

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

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

    for (auto i : l_cycles[nod])
        active.erase(active.find(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);

    global_path.insert(0);
    for (int i = 0; i <= n; i++) {
        /// fac un syslink aici
        /// -> o sa am lungimea totala pana acum h[i] + l_link
        global_path.insert(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 + length[j];
            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:80: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:86: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
0 / 33.0

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

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1152 KB Output is correct
2 Correct 18 ms 1312 KB Output is correct
3 Correct 21 ms 1408 KB Output is correct
4 Correct 20 ms 1408 KB Output is correct
5 Execution timed out 1071 ms 62584 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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