Submission #1192976

#TimeUsernameProblemLanguageResultExecution timeMemory
1192976LithaniumBitaro’s Party (JOI18_bitaro)C++20
7 / 100
2096 ms42128 KiB
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,sse,sse2,sse4,popcnt") #include <bits/stdc++.h> using namespace std; constexpr int K = 200; vector<pair<int, int>> buffer[100005]; bool seen[100005]; bool bruh[100005]; int dist[100005]; vector<int> topsort; vector<int> adj[100005]; vector<int> rev[100005]; int freq[100005]; void push(int a, int b) { for (auto [x, y]:buffer[a]) freq[y] = max(freq[y], x+1); for (auto [x, y]:buffer[b]) freq[y] = max(freq[y], x); vector<pair<int, int>> ans; for (auto [x, y]:buffer[a]) if (freq[y] != -1) { ans.push_back({freq[y], y}); freq[y] = -1; } for (auto [x, y]:buffer[b]) if (!freq[y] != -1) { ans.push_back({freq[y], y}); freq[y] = -1; } sort(ans.begin(), ans.end()); swap(buffer[b], ans); } void dfs(int n) { seen[n] = 1; for (int i:adj[n]) if (!seen[i]) dfs(i); topsort.push_back(n); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); memset(freq, -1, sizeof(freq)); int N, M, Q; cin >> N >> M >> Q; for (int i = 1; i <= N; i ++) { buffer[i].push_back({0, i}); } for (int i = 1; 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 ++) if (!seen[i]) dfs(i); reverse(topsort.begin(), topsort.end()); for (int i:topsort) for (int j:adj[i]) push(i, j); reverse(topsort.begin(), topsort.end()); for (int i = 1; i <= N; i ++) reverse(buffer[i].begin(), buffer[i].end()); for (int i = 1; i <= Q; i ++) { int T, Y; cin >> T >> Y; vector<int> banned(Y); for (int &j:banned) { cin >> j; bruh[j] = 1; } if (Y <= K) { bool skip = 0; for (auto [a, b]:buffer[T]) if (!bruh[b]) { cout << a << "\n"; skip = 1; break; } if (!skip) cout << "-1\n"; } else { memset(dist, -0x3f, sizeof(dist)); dist[T] = 0; int ans = -1; for (int j:topsort) { for (int k:rev[j]) dist[k] = max(dist[k], dist[j] + 1); if (!bruh[j]) ans = max(ans, dist[j]); } cout << ans << "\n"; } for (int j:banned) bruh[j] = 0; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...