Submission #383471

#TimeUsernameProblemLanguageResultExecution timeMemory
383471moratoBitaro’s Party (JOI18_bitaro)C++17
14 / 100
2094 ms293544 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXS = 350; vector<int> adj[MAXN], rev[MAXN]; vector<pair<int, int>> caras[MAXN]; int in[MAXN], bosta[MAXN], best[MAXN]; pair<int, int> revIn[MAXN]; bool mark[MAXN], blocked[MAXN], valid[MAXN]; void merge(vector<pair<int, int>>& a, vector<pair<int, int>> b) { vector<pair<int, int>> result; int tamA = (int) a.size(); int tamB = (int) b.size(); int i = 0, j = 0, cnt = 0; for (; i < tamA && j < tamB && cnt < MAXS + 1;) { if (mark[a[i].second]) { i++; continue; } if (mark[b[j].second]) { j++; continue; } if (a[i].first > b[j].first + 1) { mark[a[i].second] = true; result.push_back(a[i++]); } else { mark[b[j].second] = true; result.emplace_back(b[j].first + 1, b[j].second); j++; } cnt++; } for (; i < tamA && cnt < MAXS + 1; i++) { if (mark[a[i].second]) continue; cnt++; result.push_back(a[i]); } for (; j < tamB && i + j < MAXS + 1; j++) { if (mark[b[j].second]) continue; cnt++; result.emplace_back(b[j].first + 1, b[j].second); } for (i = 0; i < (int) result.size(); i++) { mark[result[i].second] = false; } a = result; } 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); in[b]++; revIn[a].first++; } for (int i = 1; i <= n; i++) { revIn[i].second = revIn[i].first; } vector<int> lista; for (int i = 1; i <= n; i++) { caras[i].push_back({0, i}); if (!in[i]) lista.push_back(i); } for (int i = 0; i < (int) lista.size(); i++) { int cur = lista[i]; for (int nxt : adj[cur]) { in[nxt]--; if (!in[nxt]) lista.push_back(nxt); merge(caras[nxt], caras[cur]); } } 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) { vector<int> llista; for (int j = 1; j <= n; j++) { best[j] = -1; revIn[j].first = revIn[j].second; if (!revIn[j].first) llista.push_back(j); } valid[t] = true; best[t] = 0; for (int j = 0; j < (int) llista.size(); j++) { int cur = llista[j]; for (int nxt : rev[cur]) { revIn[nxt].first--; if (!revIn[nxt].first) llista.push_back(nxt); if (valid[cur]) { valid[nxt] = true; best[nxt] = max(best[nxt], best[cur] + 1); } } } int ans = -1; for (int j = 1; j <= t; j++) { valid[j] = false; if (!blocked[j]) ans = max(ans, best[j]); } 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; } } // for (int i = 1; i <= n; i++) { // cout << i << " -> "; // for (auto x : caras[i]) { // cout << "(" << x.first << ", " << x.second << "), "; // } // cout << '\n'; // } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...