| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 891155 |
2023-12-22T09:07:49 Z |
nahco314 |
File Paths (BOI15_fil) |
C++14 |
|
1000 ms |
94516 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<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
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]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1176 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 4 |
Correct |
14 ms |
3268 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1628 KB |
Output is correct |
| 6 |
Correct |
11 ms |
1372 KB |
Output is correct |
| 7 |
Correct |
27 ms |
6760 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 12 |
Correct |
13 ms |
3252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
37612 KB |
Output is correct |
| 2 |
Correct |
175 ms |
37712 KB |
Output is correct |
| 3 |
Correct |
176 ms |
37460 KB |
Output is correct |
| 4 |
Correct |
177 ms |
37460 KB |
Output is correct |
| 5 |
Execution timed out |
1022 ms |
94516 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1176 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 4 |
Correct |
14 ms |
3268 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1628 KB |
Output is correct |
| 6 |
Correct |
11 ms |
1372 KB |
Output is correct |
| 7 |
Correct |
27 ms |
6760 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 12 |
Correct |
13 ms |
3252 KB |
Output is correct |
| 13 |
Correct |
179 ms |
37612 KB |
Output is correct |
| 14 |
Correct |
175 ms |
37712 KB |
Output is correct |
| 15 |
Correct |
176 ms |
37460 KB |
Output is correct |
| 16 |
Correct |
177 ms |
37460 KB |
Output is correct |
| 17 |
Execution timed out |
1022 ms |
94516 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
