Submission #218116

#TimeUsernameProblemLanguageResultExecution timeMemory
218116dolphingarlicFile Paths (BOI15_fil)C++14
0 / 100
17 ms7552 KiB
#include <bits/stdc++.h> #define FOR(i, x, y) for (int i = x; i < y; i++) typedef long long ll; using namespace std; int n, m, k, s; vector<int> graph[6001]; int to_root[6001], par[6001], can[1000001], cyc[1000001]; bool reachable[6001]; void add_cycles(int node, int root, int val) { if (node <= n) cyc[to_root[node] - to_root[root] + s] += val; for (int i : graph[node]) add_cycles(i, root, val); } void dfs(int node = 0) { if (node > n) { int add_dist = k - to_root[node]; if (add_dist == 0) reachable[node] = true; for (int i = 1; i * i <= add_dist; i++) if (add_dist % i == 0 && (cyc[i] || cyc[add_dist / i])) reachable[node] = true; for (int i = par[node]; ~i; i = par[i]) if (add_dist - s + to_root[i] >= 0 && can[add_dist - s + to_root[i]]) reachable[node] = true; } else { for (int i = node; ~i; i = par[i]) cyc[to_root[node] - to_root[i] + s]++; add_cycles(node, node, 1); for (int i : graph[node]) dfs(i); for (int i = node; ~i; i = par[i]) cyc[to_root[node] - to_root[i] + s]--; add_cycles(node, node, -1); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k >> s; s++; par[0] = -1; can[0] = 1; FOR(i, 1, n + m + 1) { int p, l; cin >> p >> l; graph[p].push_back(i); to_root[i] = to_root[p] + l + 1; par[i] = p; if (i <= n && to_root[i] <= k) can[to_root[i]]++; } dfs(); FOR(i, n + 1, n + m + 1) cout << (reachable[i] ? "YES\n" : "NO\n"); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...