Submission #535980

#TimeUsernameProblemLanguageResultExecution timeMemory
535980cig32Long Mansion (JOI17_long_mansion)C++17
5 / 100
3095 ms11304 KiB
#include "bits/stdc++.h" using namespace std; const int MAXN = 2e5 + 10; const int MOD = 1e9 + 7; #define int long long mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count()); int rnd(int x, int y) { int u = uniform_int_distribution<int>(x, y)(rng); return u; } int bm(int b, int p) { if(p==0) return 1; int r = bm(b, p/2); if(p&1) return (((r*r) % MOD) * b) % MOD; return (r*r) % MOD; } int inv(int b) { return bm(b, MOD-2); } int f[MAXN]; int nCr(int n, int r) { int ans = f[n]; ans *= inv(f[r]); ans %= MOD; ans *= inv(f[n-r]); ans %= MOD; return ans; } void precomp() { f[0] = 1; for(int i=1; i<MAXN; i++) f[i] = (f[i-1] * i) % MOD; } void solve(int tc) { int n; cin >> n; int c[n]; for(int i=1; i<n; i++)cin >> c[i]; vector<int> R[n+1]; for(int i=1; i<=n; i++) { int x;cin >> x; for(int j=0; j<x; j++) { int y;cin >> y; R[i].push_back(y); } } int q;cin >> q; while(q--) { int x, y;cin >> x >> y; int l = x, r = x; bool have[n+1]; for(int i=1; i<=n; i++) have[i] = 0; for(int z: R[x]) have[z] = 1; while(1) { if(l > 1 && have[c[l - 1]]) { l--; for(int z: R[l]) have[z] = 1; } else if(r < n && have[c[r]]) { r++; for(int z: R[r]) have[z] = 1; } else break; } cout << (l <= y && y <= r ? "YES\n" : "NO\n"); } } int32_t main(){ precomp(); ios::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; for(int i=1; i<=t; i++) solve(i); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...