제출 #383559

#제출 시각아이디문제언어결과실행 시간메모리
383559moratoBitaro’s Party (JOI18_bitaro)C++17
14 / 100
2092 ms217544 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], result; int bosta[MAXN], dp[MAXN], valid[MAXN]; bool mark[MAXN], blocked[MAXN]; void merge(int a, int b) { result.clear(); int j = 0; for (int i = 0; i < (int) caras[a].size(); i++) { for (; j < (int) caras[b].size() && caras[b][j].first + 1 > caras[a][i].first; j++) { result.push_back({caras[b][j].first + 1, caras[b][j].second}); } 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] = -1000000000; } dp[t] = 0; for (int v = n; v >= 1; v--) { for (int u : rev[v]) { dp[u] = max(dp[u], dp[v] + 1); } } int ans = -1; for (int j = 1; j <= t; j++) { if (!blocked[j]) ans = max(ans, dp[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; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...