Submission #1092124

#TimeUsernameProblemLanguageResultExecution timeMemory
10921240x34cBitaro’s Party (JOI18_bitaro)C++17
0 / 100
2036 ms8536 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define endl '\n' using namespace std; const int BLOCK_SZ = 300; const int MAX_N = 1e5 + 1; vector<int> graph[MAX_N]; bool mark[MAX_N]; vector<pii> paths[MAX_N]; int from[MAX_N]; int dfs(int v) { int ret = mark[v] ? -1 : 0; for (int u : graph[v]) { int res = dfs(u); if (res != -1) ret = max(ret, res + 1); } return ret; } void pre_comp(int v) { vector<int> cur(1, v); from[v] = 0; for (int u : graph[v]) for (pii pth : paths[u]) { from[pth.second] = max(from[pth.second], pth.first + 1); if (!mark[pth.second]) { cur.push_back(pth.second); mark[pth.second] = true; } } for (int u : cur) paths[v].push_back({from[u], u}); for (int u : cur) { mark[u] = false; from[u] = -1; } sort(paths[v].begin(), paths[v].end(), greater<pii>()); while (paths[v].size() > BLOCK_SZ) paths[v].pop_back(); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int N, M, Q; cin >> N >> M >> Q; fill_n(&from[0], N, -1); for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; --a; --b; graph[b].push_back(a); } for (int v = 0; v < N; v++) pre_comp(v); while (Q--) { int t, y; cin >> t >> y; --t; vector<int> cs(y); for (int i = 0; i < y; i++) { cin >> cs[i]; --cs[i]; mark[cs[i]] = true; } if (y >= BLOCK_SZ) cout << dfs(t) << endl; else { bool ok = false; for (pii pth : paths[t]) { if (!mark[pth.second]) { cout << pth.first << endl; ok = true; break; } } if (!ok) cout << -1 << endl; } for (int c : cs) mark[c] = false; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...