# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
201604 | 2020-02-11T12:01:54 Z | Sensei | Bitaro’s Party (JOI18_bitaro) | C++17 | 2000 ms | 10872 KB |
/* DATE: 2020-02-11 14:19:26 NAME: PROBLEM: JOI18_BITARO */ #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5; const int SQRT = 350; vector<int> edge[MAXN + 7]; vector<int> redge[MAXN + 7]; int dp[MAXN + 7]; bool vis[MAXN + 7]; vector<pair<int, int> > sqrt_furthest[MAXN + 7]; void sqrt_dfs(int u) { vis[u] = true; for (int i = 0; i < redge[u].size(); i++) { int v = redge[u][i]; if (!vis[v]) { sqrt_dfs(v); } } vector<pair<int, int> > ans; ans.push_back({0, u}); for (int i = 0; i < redge[u].size(); i++) { int v = redge[u][i]; vector<pair<int, int> > copy_ans; swap(ans, copy_ans); // copy_ans.push_back({1, v}); set<int> in; int x = 0; int y = 0; while (ans.size() < SQRT and x < sqrt_furthest[v].size() and y < copy_ans.size()) { if (in.find(sqrt_furthest[v][x].second) != in.end()) { x++; continue; } if (in.find(copy_ans[y].second) != in.end()) { y++; continue; } if (sqrt_furthest[v][x].first + 1 > copy_ans[y].first) { ans.push_back({sqrt_furthest[v][x].first + 1, sqrt_furthest[v][x].second}); in.insert(sqrt_furthest[v][x].second); } else { ans.push_back(copy_ans[y]); in.insert(copy_ans[y].second); } } while (ans.size() < SQRT and x < sqrt_furthest[v].size()) { if (in.find(sqrt_furthest[v][x].second) != in.end()) { x++; continue; } ans.push_back({sqrt_furthest[v][x].first + 1, sqrt_furthest[v][x].second}); in.insert(sqrt_furthest[v][x].second); } while (ans.size() < SQRT and y < copy_ans.size()) { if (in.find(copy_ans[y].second) != in.end()) { y++; continue; } ans.push_back(copy_ans[y]); in.insert(copy_ans[y].second); } } sqrt_furthest[u] = ans; } void naive_dfs(int u, vector<int> &disallowed) { vis[u] = true; if (binary_search(disallowed.begin(), disallowed.end(), u) == true) { dp[u] = -1; } else { dp[u] = 0; } for (int i = 0; i < redge[u].size(); i++) { int v = redge[u][i]; if (!vis[v]) { naive_dfs(v, disallowed); } if (dp[v] != -1) { dp[u] = max(dp[u], 1 + dp[v]); } } } int main() { int n, m, q; cin >> n >> m >> q; for (int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); edge[u].push_back(v); redge[v].push_back(u); } for (int u = 1; u <= n; u++) { if (!vis[u]) { sqrt_dfs(u); } } for (int i = 1; i <= q; i++) { int u; scanf("%d", &u); int cnt; scanf("%d", &cnt); vector<int> disallowed(cnt); for (int j = 0; j < cnt; j++) { scanf("%d", &disallowed[j]); } if (cnt >= SQRT) { memset(dp, 0, sizeof dp); memset(vis, 0, sizeof vis); naive_dfs(u, disallowed); printf("%d\n", dp[u]); } else { int ans = -1; for (int j = 0; j < sqrt_furthest[u].size(); j++) { if (binary_search(disallowed.begin(), disallowed.end(), sqrt_furthest[u][j].second) == false) { ans = sqrt_furthest[u][j].first; break; } } printf("%d\n", ans); } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7416 KB | Output is correct |
2 | Correct | 9 ms | 7416 KB | Output is correct |
3 | Correct | 10 ms | 7416 KB | Output is correct |
4 | Correct | 11 ms | 7416 KB | Output is correct |
5 | Correct | 28 ms | 8184 KB | Output is correct |
6 | Correct | 29 ms | 8312 KB | Output is correct |
7 | Correct | 27 ms | 8312 KB | Output is correct |
8 | Correct | 104 ms | 10360 KB | Output is correct |
9 | Correct | 103 ms | 10360 KB | Output is correct |
10 | Correct | 106 ms | 10336 KB | Output is correct |
11 | Correct | 139 ms | 10104 KB | Output is correct |
12 | Correct | 73 ms | 8824 KB | Output is correct |
13 | Correct | 138 ms | 9976 KB | Output is correct |
14 | Correct | 130 ms | 9336 KB | Output is correct |
15 | Correct | 89 ms | 8568 KB | Output is correct |
16 | Correct | 123 ms | 9208 KB | Output is correct |
17 | Correct | 111 ms | 9464 KB | Output is correct |
18 | Correct | 79 ms | 8696 KB | Output is correct |
19 | Correct | 114 ms | 9380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7416 KB | Output is correct |
2 | Correct | 9 ms | 7416 KB | Output is correct |
3 | Correct | 10 ms | 7416 KB | Output is correct |
4 | Correct | 11 ms | 7416 KB | Output is correct |
5 | Correct | 28 ms | 8184 KB | Output is correct |
6 | Correct | 29 ms | 8312 KB | Output is correct |
7 | Correct | 27 ms | 8312 KB | Output is correct |
8 | Correct | 104 ms | 10360 KB | Output is correct |
9 | Correct | 103 ms | 10360 KB | Output is correct |
10 | Correct | 106 ms | 10336 KB | Output is correct |
11 | Correct | 139 ms | 10104 KB | Output is correct |
12 | Correct | 73 ms | 8824 KB | Output is correct |
13 | Correct | 138 ms | 9976 KB | Output is correct |
14 | Correct | 130 ms | 9336 KB | Output is correct |
15 | Correct | 89 ms | 8568 KB | Output is correct |
16 | Correct | 123 ms | 9208 KB | Output is correct |
17 | Correct | 111 ms | 9464 KB | Output is correct |
18 | Correct | 79 ms | 8696 KB | Output is correct |
19 | Correct | 114 ms | 9380 KB | Output is correct |
20 | Execution timed out | 2071 ms | 10872 KB | Time limit exceeded |
21 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7416 KB | Output is correct |
2 | Correct | 9 ms | 7416 KB | Output is correct |
3 | Correct | 10 ms | 7416 KB | Output is correct |
4 | Correct | 11 ms | 7416 KB | Output is correct |
5 | Correct | 28 ms | 8184 KB | Output is correct |
6 | Correct | 29 ms | 8312 KB | Output is correct |
7 | Correct | 27 ms | 8312 KB | Output is correct |
8 | Correct | 104 ms | 10360 KB | Output is correct |
9 | Correct | 103 ms | 10360 KB | Output is correct |
10 | Correct | 106 ms | 10336 KB | Output is correct |
11 | Correct | 139 ms | 10104 KB | Output is correct |
12 | Correct | 73 ms | 8824 KB | Output is correct |
13 | Correct | 138 ms | 9976 KB | Output is correct |
14 | Correct | 130 ms | 9336 KB | Output is correct |
15 | Correct | 89 ms | 8568 KB | Output is correct |
16 | Correct | 123 ms | 9208 KB | Output is correct |
17 | Correct | 111 ms | 9464 KB | Output is correct |
18 | Correct | 79 ms | 8696 KB | Output is correct |
19 | Correct | 114 ms | 9380 KB | Output is correct |
20 | Execution timed out | 2071 ms | 10872 KB | Time limit exceeded |
21 | Halted | 0 ms | 0 KB | - |