Submission #891155

#	Time	Username	Problem	Language	Result	Execution time	Memory
891155		nahco314	File Paths (BOI15_fil)	C++14	33 / 100	1022 ms	94516 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<int>> dists;
vector<vector<bool>> is_child;
vector<bool> ans;

unordered_set<int> ds;

unordered_map<int, int> makes;

void pre_dfs(int v, int p, vector<int>& st) {
    st.push_back(v);
    for (int p : st) {
        is_child[p][v] = true;
    }
    for (auto [nxt, l] : g[v]) {
        if (nxt == p) continue;
        pre_dfs(nxt, v, 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 = dists[v][i] + 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 + dists[0][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++;

    dists = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
    is_child = vector<vector<bool>>(n + 1, vector<bool>(n + 1, false));
    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);
            }
        }
    }

    vector<int> st;
    pre_dfs(0, -1, st);

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

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