제출 #1112146

#제출 시각아이디문제언어결과실행 시간메모리
1112146Muaath_5Bitaro’s Party (JOI18_bitaro)C++17
14 / 100
1600 ms241936 KiB
// Problem: C - Bitaro's Party // Contest: Virtual Judge - Square root tech // URL: https://vjudge.net/contest/671583#problem/C // Memory Limit: 507 MB // Time Limit: 2000 ms // // By Muaath Alqarni // Blog: https://muaath5.githib.io/blog // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> #define ll long long #define pii pair<int, int> using namespace std; const int N = 1e5+5, SQ = 300; int n, m, q; vector<int> adj[N]; int len[N]; pair<int, int> dp[N][SQ]; char mp[N]; int dp2[N]; static inline int read() { int x = 0;char ch = getchar(); while (ch < '0' || ch>'9') ch = getchar(); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar(); return x; } static inline void print(const int &x) { if (x > 9)print(x / 10); putchar('0' + x % 10); } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); n=read(),m=read(),q=read(); for (int i = 0; i < m; i++) { int u=read(), v=read(); adj[v].push_back(u); } // precalc vector<pii> res; res.reserve(SQ); for (int i = 1; i <= n; i++) { len[i] = 1; dp[i][0] = {0, i}; for (int j : adj[i]) { vector<bool> used(n+1); res.clear(); int p1 = 0, p2 = 0; while (p1 < len[i] && p2 < len[j]) { if (used[dp[i][p1].second]) { p1++; continue; } if (used[dp[j][p2].second]) { p2++; continue; } if (dp[i][p1].first > dp[j][p2].first+1) used[dp[i][p1].second] = 1, res.push_back(dp[i][p1++]); else { used[dp[j][p2].second] = 1; res.push_back({dp[j][p2].first+1, dp[j][p2].second}); p2++; } } while (p1 < len[i] && res.size() < SQ) { if (!used[dp[i][p1].second]) used[dp[i][p1].second] = 1, res.push_back(dp[i][p1]); p1++; } while (p2 < len[j] && res.size() < SQ) { if (!used[dp[j][p2].second]) used[dp[j][p2].second] = 1, res.push_back({dp[j][p2].first+1, dp[j][p2].second}); p2++; } sort(res.begin(), res.end(), greater<>()); len[i] = res.size(); for (int x = 0; x < len[i]; x++) dp[i][x] = res[x]; } } while (q--) { int t=read(), y=read(); vector<int> c(y); for (int &i : c) { i=read(); mp[i] = 1; } if (y >= SQ) { for (int i = 1; i <= t; i++) { for (int prv : adj[i]) { if (!mp[prv] || dp2[prv] > 0) dp2[i] = max(dp2[i], dp2[prv]+1); } } if (dp2[t] == 0 && mp[t]) putchar('-'),putchar('1'); else print(dp2[t]); } else { bool ok = false; for (int i = 0; i < len[t]; i++) { if (!mp[dp[t][i].second]) { print(dp[t][i].first); ok = true; break; } } if (!ok) putchar('-'),putchar('1'); } putchar('\n'); for (int &i : c) { mp[i] = 0; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...