oj.uz

Submission #106293

# Submission time Handle Problem Language Result Execution time Memory
106293 2019-04-17T19:27:16 Z BigChungus File Paths (BOI15_fil) C++14
0 / 100
 16 ms 7808 KB 
#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]);///pt ca nu poti pune intr-o fila dreq
    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]) {
        if (k - h[i] < 0)
            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;
        }
    }
}

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]++;///pt ca '\'
        frz[pf[i]].push_back(i);
    }
    ///acum pt d-alea pe care le folosim doar o data
    ///arata cv gen:(0)
    ///               \
    ///                \
    ///                ...
    ///                  \
    ///      (j)---...--(i)
    ///      /
    ///     /
    ///   ...
    ///   /
    /// (f)
    ///am notat cu i, j, f = noduri, f frunza, 0 = radacina cu mentiunea ca nodurile i si j nu sunt neaparat
    ///si ----...--- este symlinkul
    dfslen();///calculam si retinem intr-un set lengths lungimile tuturor drumurilor de la radacina la un nod oarecare
    for (int i = 0; i < m; ++i) {
        int curl(s + lf[i]), curn = pf[i];///nu e 0 ca spune ca nu poti sa faci un link direct la o fila
        while (curn != 0) {
            if (lengths.find(k - curl) != lengths.end())
                bun[i] = 1;
            curl += l[curn];
            curn = p[curn];
        }
    }
    ///acum pt d-alea pe care le folosim de mai multe ori
    ///arata cv gen:(0)
    ///             /
    ///            /
    ///          ...
    ///          /
    ///        (i)----_    }
    ///        / \     \\  }
    ///       /   \     \\ }  link
    ///     ...   ...   // }
    ///     /       \  //  }
    ///    /        (j)    }
    ///   /
    /// (f)
    /// unde (i-j) = link si linkul poate sa continue mai mult pe alea drumul (i-f)
    dfsb();///retinem in lungimi toate lungimile drumurilor de tio (i-j) pe fiecare i in parte
    plimba();
    for (int i = 0; i < m; ++i) {
        if (bun[i])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

Compilation message

fil.cpp:71:5: warning: multi-line comment [-Wcomment]
     ///               \
     ^
fil.cpp:74:5: warning: multi-line comment [-Wcomment]
     ///                  \
     ^

Subtask #1
0 / 33.0

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

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 7808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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