oj.uz

Submission #891169

# Submission time Handle Problem Language Result Execution time Memory
891169 2023-12-22T09:43:00 Z nahco314 File Paths (BOI15_fil) C++14
33 / 100
 1000 ms 58796 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> get_divs(int n) {
    vector<int> res;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.push_back(n / i);
            res.push_back(i);
        }
    }
    return res;
}

int n, m, k, s;
vector<vector<pair<int, int>>> g;
vector<vector<pair<int, int>>> files;

vector<vector<bool>> is_child;
vector<bool> ans;
vector<int> pd;

unordered_set<int> ds;

unordered_map<int, int> makes;

void pre_dfs(int v, int p, int d, vector<int>& st) {
    st.push_back(v);
    pd[v] = d;
    for (int p : st) {
        is_child[p][v] = true;
    }
    for (auto [nxt, l] : g[v]) {
        if (nxt == p) continue;
        pre_dfs(nxt, v, d + l, st);
    }
    st.pop_back();
}

void dfs(int v, int p, int d) {
    vector<int> added_makes;
    for (int i = 0; i < n + 1; i++) {
        if (!is_child[v][i]) continue;
        int num = pd[i] - pd[v] + s;
        // cerr << "  make loop: " << v << " " << i << " " << num << endl;
        makes[num] = makes[num] + 1;
        added_makes.push_back(num);
    }

    ds.insert(d);

    for (auto [f_n, l] : files[v]) {
        int remain = k - d - l;

        if (remain == 0) {
            // cerr << "ans0 just: " << f_n << endl;
            ans[f_n] = true;
            continue;
        }

        for (int div : get_divs(remain)) {
            if (makes.count(div) > 0) {
                // cerr << "ans1 loop: " << f_n << " " << div << endl;
                ans[f_n] = true;
            }
        }

        for (int i = 0; i < n + 1; i++) {
            int all_cost = d + l + pd[i] + s;
            int over = all_cost - k;
            if (ds.count(over) > 0) {
                // cerr << "ans2 first jump: " << f_n << " " << i << endl;
                ans[f_n] = true;
            }
        }
    }

    for (auto [nxt, l] : g[v]) {
        if (nxt == p) continue;
        dfs(nxt, v, d + l);
    }

    for (int num : added_makes) {
        makes[num] = makes[num] - 1;
        if (makes[num] == 0) {
            makes.erase(num);
        }
    }

    ds.erase(d);
}

int main() {
    cin >> n >> m >> k >> s;
    ans = vector<bool>(m, false);
    g = vector<vector<pair<int, int>>>(n + 1);
    files = vector<vector<pair<int, int>>>(n + 1);
    for (int i = 0; i < n; i++) {
        int p, l;
        cin >> p >> l;
        g[p].emplace_back(i + 1, l + 1);
        g[i + 1].emplace_back(p, l + 1);
    }
    for (int i = 0; i < m; i++) {
        int p, l;
        cin >> p >> l;
        files[p].emplace_back(i, l + 1);
    }
    s++;

    vector<int> st;
    pd = vector<int>(n + 1);
    is_child = vector<vector<bool>>(n + 1, vector<bool>(n + 1, false));
    pre_dfs(0, -1, 0, st);

    dfs(0, -1, 0);

    for (int i = 0; i < m; i++) {
        if (ans[i]) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

Compilation message

fil.cpp: In function 'void pre_dfs(int, int, int, std::vector<int>&)':
fil.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for (auto [nxt, l] : g[v]) {
      |               ^
fil.cpp: In function 'void dfs(int, int, int)':
fil.cpp:52:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     for (auto [f_n, l] : files[v]) {
      |               ^
fil.cpp:78:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |     for (auto [nxt, l] : g[v]) {
      |               ^

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 13 ms 2740 KB Output is correct
5 Correct 9 ms 784 KB Output is correct
6 Correct 8 ms 596 KB Output is correct
7 Correct 26 ms 5828 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 6 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 15 ms 2488 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 2216 KB Output is correct
2 Correct 98 ms 2204 KB Output is correct
3 Correct 100 ms 2140 KB Output is correct
4 Correct 101 ms 2232 KB Output is correct
5 Execution timed out 1042 ms 58796 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 13 ms 2740 KB Output is correct
5 Correct 9 ms 784 KB Output is correct
6 Correct 8 ms 596 KB Output is correct
7 Correct 26 ms 5828 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 6 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 15 ms 2488 KB Output is correct
13 Correct 99 ms 2216 KB Output is correct
14 Correct 98 ms 2204 KB Output is correct
15 Correct 100 ms 2140 KB Output is correct
16 Correct 101 ms 2232 KB Output is correct
17 Execution timed out 1042 ms 58796 KB Time limit exceeded
18 Halted 0 ms 0 KB -