제출 #952209

#제출 시각아이디문제언어결과실행 시간메모리
952209BhavayGoyalBitaro’s Party (JOI18_bitaro)C++14
100 / 100
1332 ms115080 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 = 100; 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}); vi vis(n+1, 0); for (int i = 2; i <= n; i++) { vector<pii> temp; temp.pb({0, i}); for (auto ch : g[i]) { for (auto x : dp[ch]) { x.f++; temp.pb(x); } } sort(all(temp)); reverse(all(temp)); // removing the duplicates for (auto &j : temp) { if (vis[j.s]) continue; vis[j.s] = true; dp[i].pb(j); if (dp[i].size() == SQRT) break; } for (auto &j : dp[i]) vis[j.s] = false; } 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;} } if (!blocked[city]) cout << max(ans, 0) << endl; else 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...