# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
966254 | 2024-04-19T15:23:28 Z | A7med_Mousa | Bitaro’s Party (JOI18_bitaro) | C++14 | 2 ms | 604 KB |
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <array> #include <cassert> using namespace std; #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) vector<int>val; bool comp(int &a, int &b){ return val[a] > val[b]; } void solve(){ int n, m, q; cin >> n >> m >> q; vector<int>adj[n]; for (int i = 0 ; i < m; ++i){ int u, v; cin >> u >> v; --u, --v; adj[v].emplace_back(u); } vector<int>vis(n); val.resize(n); int sq = sqrt(n); vector<vector<pair<int ,int>>>dp(n); for (int node = 0; node < n; ++node){ vector<int>cur; cur.emplace_back(node); val[node] = 0; vis[node] = node; for (int &child : adj[node]){ for (auto &[value , cur_node] : dp[child]){ if (vis[cur_node] != node){ vis[cur_node] = node; val[cur_node] = value + 1; cur.emplace_back(cur_node); } else val[cur_node] = max(val[cur_node], value + 1); } } sort(cur.begin(), cur.end(),comp); int sz = (int) cur.size(); for (int i = 0; i < min(sz, sq); ++i) dp[node].emplace_back(make_pair(val[cur[i]], cur[i])); } vector<int>take(n); for (int i = 1; i <= q; ++i){ int node; cin >> node; --node; int total; cin >> total; while(total--){ int x; cin >> x; --x; take[x] = i; } if (total >= sq){ vector<int>dp1(n, -1); dp1[node] = 0; int ans = (take[node] == i ? -1 : 0); for (int j = node; j >= 0; --j){ if (take[j] != i); ans = max(ans, dp1[j]); for (int &child : adj[j]) dp1[child] = max(dp1[child], dp1[j] + 1); } cout << ans << '\n'; } else { bool x = 1; for (auto &[val, cur_node] : dp[node]) if (take[cur_node] != i){ cout << val << '\n'; x = 0; break; } if (x) cout << -1 << '\n'; } } } int main() { fast; int t = 1; //cin >> t; for (int i = 1 ; i <= t; ++i){ solve(); if (i != t) cout << '\n'; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 2 ms | 604 KB | Output is correct |
6 | Correct | 2 ms | 604 KB | Output is correct |
7 | Incorrect | 2 ms | 604 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 2 ms | 604 KB | Output is correct |
6 | Correct | 2 ms | 604 KB | Output is correct |
7 | Incorrect | 2 ms | 604 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 2 ms | 604 KB | Output is correct |
6 | Correct | 2 ms | 604 KB | Output is correct |
7 | Incorrect | 2 ms | 604 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |