Submission #104629

#	Time	Username	Problem	Language	Result	Execution time	Memory
104629		teomrn	File Paths (BOI15_fil)	C++14	100 / 100	202 ms	28344 KiB

fil

#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 (stderr)

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