Submission #383586

#TimeUsernameProblemLanguageResultExecution timeMemory
383586moratoBitaro’s Party (JOI18_bitaro)C++17
0 / 100
9 ms7916 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXS = 200; vector<int> adj[MAXN], rev[MAXN]; vector<pair<int, int>> caras[MAXN]; int dp[MAXN], bosta[MAXN]; bool mark[MAXN], blocked[MAXN], valid[MAXN]; int solve(int v) { if (dp[v] != -1) return dp[v]; int& ans = dp[v]; ans = 0; valid[v] = !blocked[v]; for (int u : rev[v]) { ans = max(ans, solve(u) + valid[u]); valid[v] |= valid[u]; } return ans; } void merge(int a, int b) { vector<pair<int, int>> result; int j = 0; for (int i = 0; i < (int) caras[a].size(); i++) { while (j < (int) caras[b].size() && caras[b][j].first + 1 > caras[a][i].first) { result.push_back({caras[b][j].first + 1, caras[b][j].second}); j++; } result.push_back(caras[a][i]); } for (; j < (int) caras[b].size(); j++) { result.push_back({caras[b][j].first + 1, caras[b][j].second}); } caras[a].clear(); for (auto x : result) { if (!mark[x.second] && (int) caras[a].size() < MAXS + 1) { caras[a].push_back(x); mark[x.second] = true; } } for (auto x : caras[a]) { mark[x.second] = false; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m, q; cin >> n >> m >> q; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); rev[b].push_back(a); } for (int i = 1; i <= n; i++) { caras[i].push_back({0, i}); for (int u : adj[i]) { merge(u, i); } } for (int i = 0; i < q; i++) { int t, y; cin >> t >> y; for (int j = 0; j < y; j++) { cin >> bosta[j]; blocked[bosta[j]] = true; } if (y > MAXS) { for (int j = 1; j <= n; j++) { dp[j] = -1; } int ans = (solve(t) ? blocked[t] ? -1 : 0 : dp[t]); cout << ans << '\n'; } else { int ans = -1; for (auto x : caras[t]) { if (!blocked[x.second]) { ans = x.first; break; } } cout << ans << '\n'; } for (int j = 0; j < y; j++) { blocked[bosta[j]] = false; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...