제출 #563718

#제출 시각아이디문제언어결과실행 시간메모리
563718thiago_bastosBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2069 ms137628 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; using u64 = unsigned long long; using ld = long double; using ii = pair<int, int>; const int N = 318; const int K = 10; const int INF = 1e9; int st[K][N]; int lg(int x) { return x ? 31 - __builtin_clz(x) : 0; } void sparse_table(vector<int>& a) { int n = a.size(); int k = 1 + lg(n); for(int i = 0; i < n; ++i) st[0][i] = a[i]; for(int i = 1; i < k; ++i) for(int j = 0; j + (1 << i) <= n; ++j) st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); } int st_query(int l, int r) { int k = 31 - __builtin_clz(r - l + 1); return max(st[k][l], st[k][r - (1 << k) + 1]); } void solve() { int n, m, q; cin >> n >> m >> q; vector<vector<int>> g(n), busy(q), query(n); vector<int> ans(q, -1); for(int i = 0; i < m; ++i) { int s, t; cin >> s >> t; --s, --t; g[s].push_back(t); } for(int i = 0; i < q; ++i) { int x, y; cin >> x >> y; busy[i].resize(y + 2); busy[i][0] = -1, busy[i][y + 1] = n; for(int j = 1; j <= y; ++j) { cin >> busy[i][j]; --busy[i][j]; } query[--x].push_back(i); } int L = sqrt(n) + 1; vector<vector<int>> dp(n); for(int i = 0; i < n; ++i) dp[i].resize(L); for(int i = 0; i < n; i += L) { for(auto& X : dp) fill(X.begin(), X.end(), -INF); int hi = min(n, i + L); for(int j = i; j < hi; ++j) dp[j][j - i] = 0; for(int j = i; j < n; ++j) for(int k : g[j]) for(int x = 0; x < L; ++x) dp[k][x] = max(dp[k][x], dp[j][x] + 1); for(int v = 0; v < n; ++v) { auto& Y = query[v]; if(Y.empty()) continue; sparse_table(dp[v]); for(int k : Y) { auto& X = busy[k]; for(int j = 1; j < (int)X.size(); ++j) { int l = max(i, X[j - 1] + 1), r = min(hi - 1, X[j] - 1); if(l > r) continue; ans[k] = max(ans[k], st_query(l - i, r - i)); } } } } for(int x : ans) cout << x << '\n'; } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...