Submission #1192970

#TimeUsernameProblemLanguageResultExecution timeMemory
1192970LithaniumBitaro’s Party (JOI18_bitaro)C++20
7 / 100
1078 ms556776 KiB
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,sse,sse2,sse4,popcnt") #include <bits/stdc++.h> using namespace std; #define int long long 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]; void push(int a, int b) { vector<pair<int, int>> temp = buffer[a], extra(buffer[a].size() + buffer[b].size()); for (pair<int, int> &t:temp) t.first ++; merge(buffer[b].begin(), buffer[b].end(), temp.begin(), temp.end(), extra.begin()); swap(extra, buffer[b]); while (buffer[b].size() > K+5) buffer[b].pop_back(); } 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); 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...