Submission #952192

#TimeUsernameProblemLanguageResultExecution timeMemory
952192BhavayGoyalBitaro’s Party (JOI18_bitaro)C++14
7 / 100
1821 ms524288 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define ll long long #define ld long double #define ar array #define vi vector<int> #define vii vector<vector<int>> #define pii pair<int, int> #define pb push_back #define all(x) x.begin(), x.end() #define f first #define s second #define endl "\n" const int MOD = 1e9+7; const int inf = 1e9; const ll linf = 1e18; const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1}; const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // -------------------------------------------------- Main Code -------------------------------------------------- const int N = 1e5+5, SQRT = 450; vi g[N]; vector<pair<int, int>> dp[N]; int blocked[N]; void sol() { int n, m, q; cin >> n >> m >> q; for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; g[b].pb(a); } dp[1].pb({0, 1}); for (int i = 2; i <= n; i++) { dp[i].pb({0, i}); for (auto ch : g[i]) { for (auto x : dp[ch]) {x.f++; dp[i].pb(x);} } sort(all(dp[i])); reverse(all(dp[i])); while (dp[i].size() > SQRT) dp[i].pop_back(); } while (q--) { int city, y; cin >> city >> y; vi cities; for (int i = 0; i < y; i++) {int x; cin >> x; cities.pb(x); blocked[x] = 1;} if (y >= SQRT) { vi dpp(n+1); for (int i = 1; i <= city; i++) { dpp[i] = (blocked[i]?-inf:0); for (auto ch : g[i]) { dpp[i] = max(dpp[i], 1+dpp[ch]); } } cout << (dpp[city]<0?-1:dpp[city]) << endl; } else { int ans = -1; for (auto &i : dp[city]) { if (!blocked[i.s]) {ans = i.f; break;} } cout << ans << endl; } // reset blocked array for (auto &i : cities) blocked[i] = 0; } } int main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; // cin >> t; while (t--) { sol(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...