Submission #1177510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177510		tnknguyen_	Long Mansion (JOI17_long_mansion)	C++20	10 / 100	3092 ms	27336 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

#define endl '\n' 
#define ll long long 
#define len(s) (int)s.size() 
#define int long long 

#define pii pair<int, int>
#define fi first
#define se second
#define MASK(k) (1LL << (k))

int n, q;
const int MX = 5e5 + 5;
vector<int> keys[MX];   
int C[MX];
pii Q[MX];

namespace SUB12{
    bool ok(){ return (n <= 5000); }
    // int ans[5005][5005], vi[MX], viid;
    int L[MX], R[MX], vi[MX], viid = 0;

    void bfs(int u){
        ++viid;
        for(int x : keys[u]) vi[x] = viid;
        for(int l=u, r=u;;){
            bool ok = 0;
            if(l > 1 && vi[C[l-1]] == viid){
                l--;
                for(int x : keys[l]) vi[x] = viid;
                ok = 1;
            }
            if(r < n && vi[C[r]] == viid){
                r++;
                for(int x : keys[r]) vi[x] = viid;
                ok = 1;
            }
            // ans[u][l] = ans[u][r] = 1;
            L[u] = l, R[u] = r;
            if(!ok) break;
        }
    }

    void solve(){
        for(int i=1; i<=n; ++i) bfs(i);
        for(int i=1; i<=q; ++i){
            int u, v; tie(u, v) = Q[i];
            if(u <= v) cout << (v <= R[u] ? "YES\n" : "NO\n");
            else cout << (L[u] <= v ? "YES\n" : "NO\n");
        }
        exit(0); ////// ///////
    }
}



int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //freopen("main.inp","r",stdin);
    //freopen("main.out","w",stdout);

    cin >> n;
    for(int i=1; i<n; ++i) cin >> C[i];
    for(int i=1; i<=n; ++i){
        int m; cin >> m;
        while(m--){
            int x; cin >> x;
            keys[i].push_back(x);
        }
    }
    cin >> q;
    for(int i=1; i<=q; ++i){
        int u, v; cin >> u >> v;
        Q[i] = {u, v};
    }

    SUB12::solve();

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 75