Submission #891173

#	Time	Username	Problem	Language	Result	Execution time	Memory
891173		nahco314	File Paths (BOI15_fil)	C++14	100 / 100	188 ms	34640 KiB

fil

#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<bool>> is_child;
vector<bool> ans;
vector<int> pd;

unordered_set<int> ds;

vector<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]++;
        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[div]) {
                // 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]--;
    }

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

    makes = vector<int>(2000020, 0);

    dfs(0, -1, 0);

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

Compilation message (stderr)

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

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