제출 #900578

#제출 시각아이디문제언어결과실행 시간메모리
900578falazBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2045 ms216656 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define F first #define S second const int N = 1e5 + 3, SQ = 503; int n, m, q, dis[N]; vector<int> radj[N]; queue<int> qu; bool mark[N]; vector<pair<int, int>> vec[N]; void bfs() { while(qu.size()) { int v = qu.front(); mark[v] = false; qu.pop(); for (auto u : radj[v]) if (dis[v] + 1 > dis[u]) { dis[u] = dis[v] + 1; if (!mark[u]) { qu.push(u); mark[u] = true; } } } } signed main(){ ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> m >> q; for (int i = 0; i < m; i++) { int v, u; cin >> v >> u; radj[u].push_back(v); } set<pair<int, int>> st; for (int i = 1; i <= n; i++) { if (radj[i].size() == 0) vec[i].push_back({i, 0}); else { for (auto v : radj[i]) { for (auto u : vec[v]) { if (dis[u.F] == 0) { dis[u.F] = u.S + 1; st.insert({dis[u.F], u.F}); } else if(dis[u.F] < u.S + 1) { st.erase({dis[u.F], u.F}); dis[u.F] = u.S + 1; st.insert({dis[u.F], u.F}); } if (st.size() > SQ) { int f = st.begin()->S; dis[f] = 0; st.erase(st.begin()); } } } while (st.size()) { int v = st.begin()->second, f = st.begin()->first; st.erase(st.begin()); vec[i].push_back({v, f}); dis[v] = 0; } vec[i].push_back({i, 0}); sort(vec[i].begin(), vec[i].end()); } } while (q--) { int t, y; cin >> t >> y; int c[y + 1]; c[y] = n + 1; for (int i = 0; i < y; i++) cin >> c[i]; if (y <= SQ) { int p = 0, ans = -1; for (int i = 0; i < int32_t(vec[t].size()); i++) { while (c[p] < vec[t][i].F) p++; if (vec[t][i].F != c[p]) ans = max(vec[t][i].S, ans); } cout << ans << endl; } else { qu.push(t); bfs(); int p = 0, ans = -1; for (int i = 1; i <= t; i++) { while (c[p] < i) p++; if (i != c[p]) ans = max(ans, dis[i]); dis[i] = 0; } cout << ans << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...