Submission #106299

#	Time	Username	Problem	Language	Result	Execution time	Memory
106299		BigChungus	File Paths (BOI15_fil)	C++14	0 / 100	16 ms	7808 KiB

fil

#include <iostream>
#include <set>
#include <vector>

using namespace std;

const int N = 3009;

bool bun[N];
int pf[N], p[N], l[N], lf[N], h[N];

vector < int > v[N], frz[N], lungimi[N];
set < int > lengths;
int frecv[(int)1e6 + 7];
int s, k;

void dfsb(int nod = 0) {
    lungimi[nod].push_back(s + l[nod]);
    for (int i : v[nod]) {
        dfsb(i);
        for (int j : lungimi[i])
            lungimi[nod].push_back(j + l[nod]);
    }
    for (int i : frz[nod]) {
        lungimi[nod].push_back(l[nod] + lf[i] + s);
    }
}

void dfslen(int nod = 0, int lgth = 0) {
    lengths.insert(lgth + s);
    for (int i : v[nod])
        dfslen(i, lgth + l[i]);
    for (int i : frz[nod])
        h[i] = lgth + lf[i];
}

void plimba(int nod = 0) {
    for (int i : lungimi[nod])
        frecv[i]++;
    for (int i : v[nod])
        plimba(i);
    for (int i : frz[nod]) {
//        cout << i << '\n';
//        for (int i = 0; i < (1e6) + 7; ++i)
//            if (frecv[i])
//                cout << i << ' ';
//        cout << '\n';
        if (k - h[i] < 0)
            continue;
        if (k == h[i]) {
            bun[i] = 1;
            continue;
        }
        int a(1);
        while (a * a <= k - h[i]) {
            if ((frecv[a] || frecv[(k - h[i]) / a]) && (k - h[i]) % a == 0)
                bun[i] = 1;
            ++a;
        }
    }
    for (int i : lungimi[nod])
        frecv[i]--;
}

int main()
{
    int n, m;
    cin >> n >> m >> k >> s;
    ++s;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i] >> l[i];
        l[i]++;
        v[p[i]].push_back(i);
    }
    for (int i = 0; i < m; ++i) {
        cin >> pf[i] >> lf[i];
        lf[i]++;
        frz[pf[i]].push_back(i);
    }
    dfslen();
//    cout << "aici \n";
//    for (int i : lengths)
//        cout << i << ' ';
//    cout << '\n';
    for (int i = 0; i < m; ++i) {
        int curl(lf[i]), curn = pf[i];
//        cout << i << '\n';
        while (curn != 0) {
            if (lengths.find(k - curl) != lengths.end())
                bun[i] = 1;
//            cout << curl << ' ';
            curl += l[curn];
            curn = p[curn];
        }
//        cout << '\n';
    }
    dfsb();
    for (int i = 0; i < m; ++i) {
//        cout << h[i] << ' ';
    }
//    cout << "\n11\n";
    plimba();
    for (int i = 0; i < m; ++i) {
        if (bun[i])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

• Subtask 1: 0 / 33
• Subtask 2: 0 / 33
• Subtask 3: 0 / 34