oj.uz

Submission #891111

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

// #pragma GCC target("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")

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<int>> dists;
vector<bool> ans;

unordered_set<int> ds;

unordered_map<int, int> makes;

void dfs(int v, int p, int d) {
    for (int i = 0; i < n + 1; i++) {
        int num = dists[v][i] + s;
        makes[num] = makes[num] + 1;
    }

    ds.insert(d);

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

        if (remain == 0) {
            ans[f_n] = true;
            continue;
        }

        for (int div : get_divs(remain)) {
            if (makes[div] > 0) {
                ans[f_n] = true;
            }
        }

        for (int i = 0; i < n + 1; i++) {
            int all_cost = d + l + dists[0][i] + s;
            int over = all_cost - k;
            if (ds.count(over) > 0) {
                ans[f_n] = true;
            }
        }
    }

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

    for (int i = 0; i < n + 1; i++) {
        int num = dists[v][i] + s;
        makes[num] = makes[num] - 1;
    }

    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++;

    dists = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
    for (int i = 0; i < n + 1; i++) {
        deque<int> q;
        vector<bool> seen(n + 1, false);
        q.push_back(i);
        seen[i] = true;
        dists[i][i] = 0;
        while (!q.empty()) {
            int v = q.front();
            q.pop_front();
            for (auto [nxt, cost] : g[v]) {
                if (seen[nxt]) continue;
                seen[nxt] = true;
                dists[i][nxt] = dists[i][v] + cost;
                q.push_back(nxt);
            }
        }
    }

    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 dfs(int, int, int)':
fil.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for (auto [f_n, l] : files[v]) {
      |               ^
fil.cpp:61:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for (auto [nxt, l] : g[v]) {
      |               ^
fil.cpp: In function 'int main()':
fil.cpp:102:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |             for (auto [nxt, cost] : g[v]) {
      |                       ^

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 8 ms 1640 KB Output is correct
3 Correct 22 ms 4668 KB Output is correct
4 Correct 19 ms 3428 KB Output is correct
5 Incorrect 34 ms 6272 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1030 ms 84476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 8 ms 1640 KB Output is correct
3 Correct 22 ms 4668 KB Output is correct
4 Correct 19 ms 3428 KB Output is correct
5 Incorrect 34 ms 6272 KB Output isn't correct
6 Halted 0 ms 0 KB -